【持续更新】二叉树相关算法

一些比较基础的二叉树相关算法。

一、二叉树遍历的非递归算法

二叉树一般用递归的方式进行遍历,因为递归其实也是用栈来实现的,所以要写二叉树的非递归遍历算法,也要用到栈来辅助。

下面是前序、中序、后序三种遍历方式的非递归代码。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#!/usr/local/env python
# -*- coding: utf-8 -*-
#
# 二叉树非递归遍历
#


# 定义二叉树节点
class TreeNode():
def __init__(self, x):
self.val = x
self.left = None
self.right = None


# 代表访问节点的操作
def visit(node):
print node.val,


# 前序遍历
def preorder_unrec(node):
stack = [] # 创建一个栈
p = node
while p is not None or len(stack) != 0:
while p is not None:
visit(p) # 访问节点
stack.append(p)
p = p.left
if len(stack) != 0:
p = stack.pop()
p = p.right


# 中序遍历
def inorder_unrec(node):
stack = [] # 创建一个栈
p = node
while p is not None or len(stack) != 0:
while p is not None:
stack.append(p)
p = p.left
if len(stack) != 0:
p = stack.pop()
visit(p) # 访问节点
p = p.right


# 后序遍历
def postorder_unrec(node):
stack = [] # 创建一个栈
p = node
pre = None # 用来记录前一个访问的节点
while p is not None or len(stack) != 0:
while p is not None:
stack.append(p)
p = p.left
if len(stack) != 0:
p = stack[len(stack) - 1] # 取栈顶元素,但不退栈(因为要先访问其右节点,现在退栈,等会就没法访问该节点了)
if p.right is None or p.right == pre: # 表明当前 p 节点的左右孩子都已经访问了
stack.pop() # 这时候才退栈
visit(p) # 访问节点
pre = p
p = None # 访问完当前 p,则下次需要访问栈内的元素,所以 p 需要置为 None,否则下次又要循环访问当前 p 了
else:
p = p.right


# 测试
if __name__ == '__main__':

# 构造一棵二叉树
# 1
# / \
# 2 3
# / \ \
# 4 5 6
# /
# 7
node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)
node7 = TreeNode(7)

node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node5.left = node7
node3.right = node6

# 测试
preorder_unrec(node1) # 前序遍历,输出 1 2 4 5 7 3 6
# inorder_unrec(node1) # 中序遍历,输出 4 2 7 5 1 3 6
# postorder_unrec(node1) # 后序遍历,输出 4 7 5 2 6 3 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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#!/usr/local/env python
# -*- coding: utf-8 -*-
#
# 已知二叉树前序遍历和中序遍历结果,求后序遍历结果
#

import sys


# 定义二叉树节点
class TreeNode():
def __init__(self, x):
self.val = x
self.left = None
self.right = None


# 代表访问节点的操作
def visit(node):
print node.val,


# 根据前序、中序遍历结果创建二叉树
def create_tree(preorder, inorder):
# 退出递归的条件
if len(preorder) == 0 or len(inorder) == 0:
return None

# 前序遍历的第一个节点一定是根节点,由此找出中序遍历数组中的根节点位置
for i in range(len(inorder)):
if preorder[0] == inorder[i]:
break

# 然后将两个遍历数组都分成两部分
if i == len(inorder) - 1: # 加这个 if 判断是为了防止切片的时候数组越界
left_preorder = preorder[1:]
right_preorder = []
left_inorder = inorder[:len(inorder) - 1]
right_inorder = []
else:
left_preorder = preorder[1:1 + i]
right_preorder = preorder[1 + i:]
left_inorder = inorder[:i]
right_inorder = inorder[i + 1:]

# 递归创建二叉树
root = TreeNode(preorder[0])
root.left = create_tree(left_preorder, left_inorder)
root.right = create_tree(right_preorder, right_inorder)

return root


# 后序遍历
def postorder(node):
p = node
if p is not None:
postorder(p.left)
postorder(p.right)
visit(p)


# 测试
if __name__ == '__main__':

preorder = map(int, sys.stdin.readline().strip().split())
inorder = map(int, sys.stdin.readline().strip().split())

# 根据前序和中序,创建该二叉树
root = create_tree(preorder, inorder)

# 后序遍历该二叉树,即可得到结果
postorder(root)

三、求二叉树中两个节点的最近公共祖先节点

可以用递归的方式从下往上来寻找,如果某个节点就是已知两个节点中的一个,则将其传给它的父节点,否则就返回 None。如果当前节点的左右子树都返回的是非 None 节点,则说明两个节点分别在当前节点的左右子树中,则当前节点就是最近的公共祖先节点。否则必然在当前节点的某一边的子树中。

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
60
61
62
63
64
65
#!/usr/local/env python
# -*- coding: utf-8 -*-
#
# 求二叉树中,已知两个节点,求其最近的公共祖先节点
#


# 定义二叉树节点
class TreeNode():
def __init__(self, x):
self.val = x
self.left = None
self.right = None


def find_common_ancestor(root, node1, node2):
# 走到了叶子节点,说明当前子树没有包含所给出的两个节点
if root is None:
return None

# 找到了就回传到上一层
if root == node1 or root == node2:
return root

# 递归寻找
left_result = find_common_ancestor(root.left, node1, node2)
right_result = find_common_ancestor(root.right, node1, node2)

# 当前节点的左右子树都包含给出的节点,则当年节点就是最近的公共祖先节点
if left_result is not None and right_result is not None:
return root
# 否则两个节点都在一边,则公共祖先节点就是寻找到了的那一边
else:
return left_result if left_result is not None else right_result


# 测试
if __name__ == '__main__':

# 构造一棵二叉树
# 1
# / \
# 2 3
# / \ \
# 4 5 6
# /
# 7
node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)
node7 = TreeNode(7)

node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node5.left = node7
node3.right = node6

# 测试,寻找 node4 和 node7 的公共祖先节点,输出结果为 2,即 node2 节点
result_node = find_common_ancestor(node1, node4, node7)
print result_node.val

四、找出二叉树中根节点到所有叶子节点的路径

只要定义一个全局栈,递归进入下一层的时候,节点进栈,递归回到上一层的时候节点出栈,到达叶子节点时,栈中存储的即是根节点到当前叶子节点的路径。

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
60
61
62
63
64
65
66
67
68
69
#!/usr/local/env python
# -*- coding: utf-8 -*-
#
# 找出二叉树中根节点到所有叶子节点的路径
#


# 定义二叉树节点
class TreeNode():
def __init__(self, x):
self.val = x
self.left = None
self.right = None


# 打印出路径
def print_path():
for i in range(len(stack)):
if (i == len(stack) - 1):
print stack[i].val
else:
print stack[i].val,


# 创建一个全局栈,用来存储路径
stack = []


def find_path(node):
if node is not None:
stack.append(node) # 从上往下走,节点进栈

if node.left is None and node.right is None:
print_path() # 到达叶子节点,则打印路径

find_path(node.left)
find_path(node.right)

stack.pop() # 从下往上走,节点出栈


# 测试
if __name__ == '__main__':

# 构造一棵二叉树
# 1
# / \
# 2 3
# / \ \
# 4 5 6
# /
# 7
node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)
node7 = TreeNode(7)

node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node5.left = node7
node3.right = node6

# 测试
find_path(node1)

五、判断一棵二叉树是不是包含另外一棵二叉树

一棵二叉树包含另外一棵二叉树,即表示包含的二叉树与另一棵二叉树中的某一部分一模一样,包括结构和节点值。要判断是否包含,首先要在第一棵二叉树上找出与被包含的二叉树的根节点相同的节点,然后从这个节点开始逐个节点判断。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#!/usr/local/env python
# -*- coding: utf-8 -*-
#
# 判断一棵二叉树是不是包含另外一棵二叉树,约定空树不是任意一个树的子结构
#


# 定义二叉树节点
class TreeNode():
def __init__(self, x):
self.val = x
self.left = None
self.right = None


def hasSubtree(root1, root2):
result = False
# 两棵树有一棵为空,就不包含
if root1 is not None and root2 is not None:
# 如果当前根节点值相同,则判断A当前根节点对应子树是否包含B
if root1.val == root2.val:
result = oneHasAnother(root1, root2)
# 递归判断树A的左子树寻找与树B根节点相同的节点
if result is False:
result = hasSubtree(root1.left, root2)
# 递归判断树A的左子树寻找与树B根节点相同的节点
if result is False:
result = hasSubtree(root1.right, root2)
return result


# 逐个节点判断一棵树是否包含另一棵
def oneHasAnother(root1, root2):
# 如果树B没有子树了,树A可能有可能没有子树,表明树A包含树B
if root2 is None:
return True
# 如果树B还有子树,而树A反而没有了,则不包含
if root1 is None:
return False
# 当前对应节点不同,则不包含
if root1.val != root2.val:
return False
# 递归判断左右子树
left_result = oneHasAnother(root1.left, root2.left)
right_result = oneHasAnother(root1.right, root2.right)
return left_result and right_result


# 测试
if __name__ == '__main__':

# 构造二叉树 A
# 1
# / \
# 2 3
# / \ \
# 4 5 6
# /
# 7
node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)
node7 = TreeNode(7)

node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node5.left = node7
node3.right = node6

# 构造二叉树 B
# 2
# \
# 5
# /
# 7
node8 = TreeNode(2)
node9 = TreeNode(5)
node10 = TreeNode(7)

node8.right = node9
node9.left = node10

# 测试
result = hasSubtree(node1, node8)
print result