吴良超的学习笔记

二叉树的遍历方法

二叉树的遍历方法有三种,分别是前序遍历,中序遍历和后序遍历。其中的前、中、后分别表示根节点在遍历中被访问的次序。因此,各个遍历方式的访问顺序如下所示:

前序遍历:根节点–>左子树–>右子树
中序遍历:左子树–>根节点–>右子树
后序遍历:左子树–>右子树–>根节点

下面通过 python 分别实现这三种遍历的递归方法和非递归方法,首先定义每个节点如下所示

1
2
3
4
5
6
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None

前序遍历

递归实现

递归实现的方法非常简单,就是先访问根节点,然后访问左子树,最后访问右子树即可。实现代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
def preorderTraversal(root):
"""
:type root: TreeNode
:rtype: List[int]
"""

result = []
if root == None:
return result
result.append(root.val)
result += preorderTraversal(root.left)
result += preorderTraversal(root.right)
return result

非递归实现

非递归的方法通过栈来实现,流程如下
(1)将根节点设为当前节点
(2)记录当前节点C的值,然后将C入栈,将当前节点设为C的左子节点
(3)重复步骤(2)直到访问到空叶子节点,然后从栈中弹出一个元素D,并将当前节点设为D的右子节点,重复步骤(2)
(4)重复步骤(2)~(3)直到栈为空

实现代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def preorderTraversal(root):
"""
:type root: TreeNode
:rtype: List[int]
"""

stack, result = [], []
curr_node = root
while len(stack) != 0 or curr_node!= None:
if curr_node != None:
result.append(curr_node.val)
stack.append(curr_node)
curr_node = curr_node.left
else:
tmp = stack.pop()
curr_node = tmp.right
return result

中序遍历

递归实现

递归实现也非常简单,按照顺序访问即可,实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
def inorderTraversal(root):
"""
:type root: TreeNode
:rtype: List[int]
"""

result = []
if root == None:
return result
result += inorderTraversal(root.left)
result.append(root.val)
result += inorderTraversal(root.right)
return result

非递归实现

非递归实现的过程类似于前序遍历的非递归实现,只是在记录节点的时间不同,中序周游记录是在元素从栈里弹出的时候才记录元素的值。实现的步骤如下:

(1)将根节点设为当前节点
(2)将当前节点C入栈,然后将当前节点设为C的左子节点
(3)重复步骤(2)直到访问到空叶子节点,然后从栈中弹出一个元素D,记录元素D的值,并将当前节点设为D的右子节点,重复步骤(2)
(4)重复步骤(2)~(3)直到栈为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def inorderTraversal( root):
"""
:type root: TreeNode
:rtype: List[int]
"""

stack, result= [], []
curr_node = root
while len(stack) != 0 or curr_node != None:
if curr_node != None:
stack.append(curr_node)
curr_node = curr_node.left
else:
tmp = stack.pop()
result.append(tmp.val)
curr_node = tmp.right
return result

后序遍历

递归实现

后序遍历的实现也非常简单,只需要按照顺序访问即可,实现代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
def postorderTraversal(root):
"""
:type root: TreeNode
:rtype: List[int]
"""

result = []
if root == None:
return result
result += postorderTraversal(root.left)
result += postorderTraversal(root.right)
result.append(root.val)
return result

非递归实现

后续遍历的非递归实现利用了一点小技巧,就是先进行根节点-->右子树-->左子树的遍历,然后将得到的结果进行反转(reverse)即可。这是因为当根节点最后访问时无法确定何时该记录这个值。

实现的过程也类似于前序遍历,具体过程如下:
(1)将根节点设为当前节点
(2)记录当前节点C的值,然后将C入栈,将当前节点设为C的右子节点
(3)重复步骤(2)直到访问到空叶子节点,然后从栈中弹出一个元素D,并将当前节点设为D的左子节点,重复步骤(2)
(4)重复步骤(2)~(3)直到栈为空

实现代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""

stack, result = [], []
curr_node = root
while len(stack)!=0 or curr_node != None:
if curr_node != None:
result.append(curr_node.val)
stack.append(curr_node)
curr_node = curr_node.right
else:
tmp = stack.pop()
curr_node = tmp.left
result.reverse()
return result