BM 36 判断是不是平衡二叉树
url：牛客
BM36
考察知识点：二叉树遍历，递归
平衡二叉树的定义：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
诀窍：自顶向下递归时传递深度，避免向上合并时重复计算深度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
class Solution:
def IsBalanced_Tree(self, left: TreeNode, right: TreeNode, current_depth: int):
if left is None and right is None:
return True, current_depth
left_depth = current_depth
right_depth = current_depth
if left is not None:
isbalanced_tree, left_depth = self.IsBalanced_Tree(left.left, left.right, current_depth+1)
if not isbalanced_tree:
return False, current_depth
if right is not None:
isbalanced_tree, right_depth = self.IsBalanced_Tree(right.left, right.right, current_depth+1)
if not isbalanced_tree:
return False, current_depth
if abs(left_depth - right_depth) > 1:
return False, current_depth
else:
return True, max(left_depth, right_depth)
def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
if pRoot is None:
return True
result, depth = self.IsBalanced_Tree(pRoot.left, pRoot.right, 0)
return result
|
BM 38
在二叉树中找到两个节点的最近公共祖先
url：牛客
BM38
建议和BM 37
在二叉搜索树中找到两个节点的最近公共祖先结合起来做。二叉搜索树由于可以提前预测节点大致位置，因此不需要对树做深度/广度的搜索。但相反如果是普通二叉树，要找某个节点就非得使用搜索技术不可。这里可以使用深度优先为代表的前序遍历来分别搜索两个节点，并获取路径。实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
class Solution:
def getPath(self, root: TreeNode, target: int):
stack = [root]
pre = {root.val: None}
while len(stack) > 0:
node = stack.pop()
if node.val == target:
break
if node.right is not None:
pre[node.right.val] = node.val
stack.append(node.right)
if node.left is not None:
pre[node.left.val] = node.val
stack.append(node.left)
path = []
cur = target
while cur is not None:
path.append(cur)
cur = pre[cur]
path.reverse()
return path
def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
path1 = self.getPath(root, o1)
path2 = self.getPath(root, o2)
min_length = min(len(path1), len(path2))
i = 0
while path1[i] == path2[i]:
i += 1
if i >= min_length:
break
return path1[i-1]
|
当然，要是使用广度优先搜索也能搜索到节点并且得到路径。对二叉树的广度优先搜索即层次遍历，依赖队列实现。具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
class Solution:
def getPath(self, root: TreeNode, target: int):
queue = [root]
pre = {root.val: None}
while len(queue) > 0:
node = queue.pop(0)
if node.val == target:
break
if node.left is not None:
pre[node.left.val] = node.val
queue.append(node.left)
if node.right is not None:
pre[node.right.val] = node.val
queue.append(node.right)
path = []
cur = target
while cur is not None:
path.append(cur)
cur = pre[cur]
path.reverse()
return path
def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
path1 = self.getPath(root, o1)
path2 = self.getPath(root, o2)
min_length = min(len(path1), len(path2))
i = 0
while path1[i] == path2[i]:
i += 1
if i >= min_length:
break
return path1[i-1]
|
值得注意的是，二叉树知道子节点并不能直接访问父节点，但是要知道路径的话在搜索到该节点之后非得要往上访问父节点才能求得路径。因此，在搜索时预先设定一个字典记录一下子节点到父节点的路径会让导出路径变得简单。
最后，这个找两个节点的最近公共祖先就变成了找路径上最后一个相同的节点了。
