二叉树遍历以及延伸
1. 二叉树先序、中序、后序层次遍历
1.1. 先序遍历
1.1.1. 递归实现
# traversal用于递归，preorderTravelsal中使用res用于保存递归的输出结果。
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def traversal(self, res, root):
if root:
res.append(root.val)
self.traversal(res, root.left)
self.traversal(res, root.right)
def preorderTraversal(self, root: TreeNode):
res = []
self.traversal(res, root)
return res 1.1.2. 非递归写法
过程：
- 初始化栈stack，将根节点添加到栈中
- 当栈不为空时
- 弹出栈顶元素tmp，并将值添加到res中。
- tmp右子树非空，将右子树入栈。
- tmp左子树非空，将左子树入栈。
由于栈是“先进后出”的顺序，所以右子树先入栈，从而使得结果为“根-左-右”。
class Solution:
def preorderTraversal(self, root: TreeNode):
if root is None:
return []
res, stack = [], [root]
while stack:
tmp = stack.pop() # 弹出栈顶元素
if tmp:
res.append(tmp.val) # 输出根值
if tmp.right:
stack.append(tmp.right)
if tmp.left:
stack.append(tmp.left)
return res 小结：递归实现时，是函数自己调用自己，一层层的嵌套下去，操作系统自动帮我们用 栈 来保存每个调用的函数，而非递归就需要我们自己模拟这样的调用过程。
1.1.3. 模板解法
参考here
思路：
- 首先，将所有根节点root的所有左孩子入栈并将值加入到结果中，直至root为空。
- 然后每弹出一个栈顶元素tmp，就访问它的右孩子。然后在将该节点当做root重新按照步骤1来一遍，直至栈为空。
class Solution:
def preorderTraversal(self, root: TreeNode):
if root is None:
return []
res, stack = [], []
while stack or root:
while root: # 循环直至所有左孩子入栈
res.append(root.val) # 值加入到res中
stack.append(root)
root = root.left
tmp = stack.pop()
root = tmp.right
return res 1.2. 中序遍历
1.2.1. 递归实现
思路：只是在递归的时候修改访问顺序即可，可以对比先序遍历的递归代码。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def traversal(self, res, root):
if root:
self.traversal(res, root.left)
res.append(root.val)
self.traversal(res, root.right)
def inorderTraversal(self, root: TreeNode):
if root is None:
return []
res = []
self.traversal(res, root)
return res 1.2.2. 非递归实现
思路：参考动画演示
由于中序遍历是左-根-右，因此，首先需要找到最左侧的节点的位置，然后输出该节点的值。然后将该节点右侧压入栈中，重复操作，直至栈空或root为空。
class Solution:
def inorderTraversal(self, root: TreeNode):
if root is None:
return []
res, stack = [], []
while stack or root:
if root:
stack.append(root)
root = root.left
else:
tmp = stack.pop()
res.append(tmp.val)
root = tmp.right
return res 1.2.3. 模板解法
相对于先序遍历的解法，只用修改一下res.append()的位置在pop()之后即可。
class Solution:
def inorderTraversal(self, root: TreeNode):
if root is None:
return []
res, stack = [], []
while stack or root:
while root:
stack.append(root)
root = root.left
tmp = stack.pop()
res.append(tmp.val)
root = tmp.right
return res 1.3. 后序遍历
1.3.1. 递归实现
class Solution:
def postorderTraversal(self, root: TreeNode):
res = []
self.traversal(res, root)
return res
def traversal(self, res, root):
if root:
self.traversal(res, root.left)
self.traversal(res, root.right)
res.append(root.val) 1.3.2. 非递归实现
思路：与先序遍历的非递归实现很相似，在压入栈的时候，先压入左子树，在压入右子树，同时最后返回值的时候返回res的倒序。
class Solution:
def postorderTraversal(self, root: TreeNode):
if not root:
return []
res, stack = [], [root]
while stack:
tmp = stack.pop()
res.append(tmp.val)
if tmp.left:
stack.append(tmp.left)
if tmp.right:
stack.append(tmp.right)
return res[::-1] 1.3.3. 模板解法
思路：与前序遍历相比，修改里层while循环的left->right，外层while循环的right->left，然后res逆序即可。
class Solution:
def postorderTraversal(self, root: TreeNode):
if root is None:
return []
res, stack = [], []
while stack or root:
while root:
stack.append(root)
res.append(root.val)
root = root.right
tmp = stack.pop()
root = tmp.left
return res[::-1] 1.4. 层次遍历
1.4.1. 递归实现
class Solution:
def helper(self, root, level, levels):
"""
levels：保存每一层的值。
level: 表示当前所在层数。根节点在第0层。
root：表示每次递归时的根节点。
"""
# 当level与len(levels)相等时，此时表示该层还没有创建对应的list用来保存该层的数值，
# 因此在levels最后增加一个索引为level的空list。
if level == len(levels):
levels.append([])
levels[level].append(root.val) # 将树节点对应的值放在对应的层次。
if root.left:
self.helper(root.left, level+1, levels) # 这里表示遍历对应的左子树。
if root.right:
self.helper(root.right, level+1, levels)
def levelOrder(self, root: TreeNode):
levels = []
self.helper(root, 0, levels)
return levels 输入和输出结果
1 / \ 2 3 / / 4 5 输出：[[1], [2, 3], [4, 5]]
修改上面代码，使的当不存在左子树或右子树的时候，就是用None替代
class Solution:
def helper(self, root, level, levels):
if level == len(levels):
levels.append([])
if root:
levels[level].append(root.val) # 将树节点对应的值放在对应的层次。
self.helper(root.left, level + 1, levels) # 这里表示遍历对应的左子树。
self.helper(root.right, level + 1, levels)
else:
levels[level].append(None)
def levelOrder(self, root: TreeNode):
levels = []
self.helper(root, 0, levels)
return levels[:-1] # 最后一列会保存多余的None，因此将其删掉。 输入和输出结果
1 / \ 2 3 / / 4 5 输出：[[1], [2, 3], [4, None, 6, None]]
1.4.2. 非递归实现（迭代实现）
二叉树的层次遍历的迭代方法与前面的不同，前面的方法都采用深度优先搜索的方式，而层次遍历使用广度优先搜索，广度优先搜索主要使用 队列 实现，因此前面的模板解法就不可使用了。
步骤：
- 初始化队列queue，并将根节点保存在添加到队列中。
- 当队列不为空时：
- 计算队列里面元素的长度size
- 循环size，保存结果到level中
- 同时添加左右子树到队列中。
- 当遍历到size之后，就将level添加到res中。
class Solution:
def levelOrder(self, root: TreeNode):
if not root:
return []
res, queue = [], [root]
while queue:
size = len(queue) # 当前队列中的节点数
level = [] # 分层存储
for i in range(size): # 遍历size次，也就是将该层所有节点的值都保存在level中
tmp = queue.pop()
level.append(tmp.val)
if tmp.left:
queue.insert(0, tmp.left)
if tmp.right:
queue.insert(0, tmp.right)
res.append(level)
return res 
远景公司福利 157人发布
投递字节跳动等公司10个岗位 >