二叉树的遍历
TIP
树的节点值一般都是简写为 val，所以放心大胆地用吧。
递归遍历
递归遍历二叉树时，每个节点都有三个特殊时刻：
- 1️⃣ 初次进入当前节点
- 2️⃣ 遍历完左子节点后返回当前节点
- 3️⃣ 遍历完右子节点后返回当前节点
py
def f(root):
if root is None:
return
# 1️⃣ 初次进入当前节点
f(root.left)
# 2️⃣ 遍历完左子节点后返回当前节点
f(root.right)
# 3️⃣ 遍历完右子节点后返回当前节点在这三个特殊的时刻，做对应的操作，将会有不同的特点。比如在这三个特殊的时刻打印当前节点值：
- 1️⃣ 时刻打印节点值为 先序遍历(pre-order): 头左右。
- 2️⃣ 时刻打印节点值为 中序遍历(in-order): 左头右。
- 3️⃣ 时刻打印节点值为 后序遍历(post-order):左右头。
js
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
const ans = []
const pre = head => {
if (!head) return
ans.push(head.val)
pre(head.left)
pre(head.right)
}
pre(root)
return ans
}js
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
const ans = []
const inorder = head => {
if (!head) return
inorder(head.left)
ans.push(head.val)
inorder(head.right)
}
inorder(root)
return ans
}js
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
const ans = []
const post = head => {
if (!head) return
post(head.left)
post(head.right)
ans.push(head.val)
}
post(root)
return ans
}非递归遍历
最开始的程序都是不支持递归的，之后的系统也是利用栈实现的递归，所以任何递归都可以改成非递归，只不过是自己管理栈的问题罢了。
为什么非递归遍历是重点:
- 递归遍历太简单了。
- 非递归遍历能够让你更熟悉二叉树结构。
- 非递归可以节省空间，因为系统栈管理的是函数，自己创建的栈可以自定指定元素大小和类型。
- 非递归执行效率更高，递归涉及函数调用和上下文切换的开销，而非递归直接通过循环实现。
【关键点】：节点形式的二叉树，访问任意一个节点，都 必须通过头节点 访问。 牢记这一点可以更好的理解下面非递归的写法。
先序 (preorder)
对每一颗子树，都是先打印“头”，然后打印左，再打印右。 重点在于，打印“左” 时，这个 左子节点 同时也是 头节点。 所以打印完这个 左子节点 后还要继续往左边打印。
当我们打印头后，头节点就只剩下“帮我们找到左右两个子节点”这一个使命，如果完成了这个使命，那么头节点就没用了。 这个时候我们可以不存储头节点的信息。 （这就是和递归不同的地方，递归实现先序遍历时，只有当左右两个子节点处理完成后，头节点才能“出栈”）
故非递归实现先序遍历的本质就是：用一个“头”，换两个“子”：
- 头出栈，然后将两个子节点入栈。 头先出栈，免得占用空间。 同时头出栈后直接打印。
- 先压右节点，再压左节点。 因为栈的结构是先进后出，而我们是在出栈时打印，所以要后压左节点，才能实现先打印左节点。
py
def pre_order_binary_tree(root, print_arr):
stack = [root]
while len(stack) != 0:
# 头节点的使命(打印, 找到子节点)在一个循环中就能完成,
# 所以不需要继续保存头节点
head = stack.pop()
print_arr.append(head.val)
# 我们是在出栈时打印, 所以先打印的东西要后压栈, 后打印的东西要先压栈
stack.append(head.right) if head.right is not None else None
stack.append(head.left) if head.left is not None else Nonejs
function preorderTraversal(root) {
const ans = []
if (!root) return ans
const stack = [root]
while (stack.length > 0) {
const head = stack.pop()
ans.push(head.val)
// 记得入栈是先右后左哦
if (head.right) stack.push(head.right)
if (head.left) stack.push(head.left)
}
return ans
}js
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
const ans = []
const stack = [root]
while (stack.length > 0){
const head = stack.pop()
// 我们可以选择在这里进行空节点的判断
if (!head) continue
ans.push(head.val)
// 颠倒
stack.push(head.right)
stack.push(head.left)
}
return ans
}后序(postorder)
后序遍历，左右头。 他其实是先序打印的变体。 先序打印中，头出栈时就打印，然后先右后左，结果就是 头左右。 将先序打印改成这样: 头出栈时打印，然后压栈顺序变为先左后右， 那结果就会变成 头右左。我们会发现这个顺序刚好和后序遍历的顺序相反， 所以只要我们将“打印”这个操作换成“入另外一个栈”，然后等待结束后， 再将另外一个栈中的内容取出，就实现了后序遍历。
py
def pos_order_binary_tree(root, print_arr):
stack = [root]
collect = [] # 收集要要打印的元素
while len(stack) != 0:
head = stack.pop()
collect.append(head) # 将打印换成入栈
# 压栈顺序变为先左后右
stack.append(head.left) if head.left is not None else None
stack.append(head.right) if head.right is not None else None
# 现在，将 collect 中的内容取出来，就是后序遍历的结果了
while len(collect) != 0:
print_arr.append(collect.pop().val)js
function postorderTraversal(root) {
if (!root) return []
const ans = []
const stack = [root]
const postStack = []
while (stack.length > 0) {
const head = stack.pop()
postStack.push(head.val)
// 这里就是负负得正，所以是 left, right
// 第一个负，指的是先序遍历中，stack 需要反着入栈
// 第二个负，指的是我们后面对 postStack 再次取反
// 所以这里需要再负一次，结果就变成了正！
if (head.left) stack.push(head.left)
if (head.right) stack.push(head.right)
}
return postStack.toReversed()
}js
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
const reversedAns = []
const stack = [root]
while (stack.length > 0) {
const head = stack.pop()
if (!head) continue
// 后序，要的是 左右头
// 所以我们的 reversedAns 中应该存储 头右左
reversedAns.push(head.val)
// 这里是放入栈中，我们需要右左，所以放入时应该是左右
stack.push(head.left)
stack.push(head.right)
}
// 出栈后返回的结果就是后序遍历结果 左右头
return reversedAns.toReversed()
}中序(inorder)
中序遍历中，头节点的使命依旧有两个：打印 + 找到两个子节点。 但因为中序遍历是 左头右，而我们选择在出栈时打印， 所以在没有打印“左”之前，头必须待在栈中。 直到“左”出栈后，头才可以出栈，同时将“右”入栈(给出右的位置)。
所以中序遍历算法如下：
- 将左子节点压栈 (“头”给出“左”的位置)
- “左”为空时，“头”出栈，同时将“右”压栈 (给出“右”位置)。
如果还不理解，自己画一下栈的变化图。
py
def in_order_binary_tree(root, print_arr):
stack = []
p = root
# 当根节点的左部都遍历完时，栈会是空的，
# 但此时并不代表遍历结束，因为 p 为根节点的右子节点。
# 所以还需继续循环，条件是 p 不为空
while len(stack) != 0 or p is not None:
if p is not None:
# 不断将左边界压栈
stack.append(p)
p = p.left
else:
# 左边界压完了，“头”的使命也就结束了, 于是“头”出栈
p = stack.pop()
print_arr.append(p.val)
# 同时“头”给出右子节点的位置
p = p.rightjs
function inorderTraversal(root) {
const inorder = []
const stack = []
let p = root
while (stack.length > 0 || p) {
// 2. 因为在添加之前，我们已经进行了判断
if (p) {
stack.push(p)
p = p.left
} else {
// 1. 我们这里保证 head 不为 null
const head = stack.pop()
inorder.push(head.val)
p = head.right
}
}
return inorder
}【为什么这样能够实现后序遍历】： 一棵树可以分解为若干个左树。不同左树之间，我们先处理左边的左树。 在处理左树时，我们是先自上到下将所有左子节点入栈，然后再出栈打印， 所以打印的顺序是先左后头。 又因为左边的左树始终比右边的左树先处理，而处理完左树的同时也会打印头， 所以最终是左头右的顺序。 对于任何一棵子树，都是让他先左再头，然后在他的右子树上， 继续先左再头。
左头右
左 左头右
左 左 左头右
左 左 左 左头右
左 左 左 ...层序 (level)
层序遍历真的很简单，只需要一个队列就可以实现
- 初始时队列里是头节点。
- 不断从队列中弹出一个节点
- 弹出节点时, 处理将该节点 (打印)
- 同时将该节点的左节点, 右节点按序加入队列中
py
from queue import Queue
def levelOrder(root):
if root is None:
return
queue = Queue()
queue.put(root)
while not queue.empty():
cur = queue.get()
print(cur.val)
if cur.left is not None:
queue.put(cur.left)
if cur.right is not None:
queue.put(cur.right)js
var printFromTopToBottom = function(root){
if (!root) return []
const queue = [root]
const ans = []
while (queue.length > 0) {
const head = queue.shift()
ans.push(head.val)
if (head.left) queue.push(head.left)
if (head.right) queue.push(head.right)
}
return ans
}层序，分层
js
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if (!root) return []
const queue = [root]
const ans = []
while (queue.length > 0) {
let curLevelSize = queue.length
ans.push([])
while (curLevelSize > 0) {
curLevelSize--
const cur = queue.shift()
ans.at(-1).push(cur.val)
if (cur.left) queue.push(cur.left)
if (cur.right) queue.push(cur.right)
}
}
return ans
}js
/**
* @param {TreeNode} root
* @return {number[][]}
*/
function levelOrder(root) {
if (!root) return []
let queue = [root]
const ans = []
// 双数组
let curLevel
let nextLevel
while (queue.length > 0) {
let curLevelSize = queue.length
curLevel = []
nextLevel = []
while (curLevelSize > 0) {
curLevelSize--
const cur = queue.shift()
curLevel.push(cur.val)
if (cur.left) nextLevel.push(cur.left)
if (cur.right) nextLevel.push(cur.right)
}
queue = nextLevel
ans.push(curLevel)
}
return ans
}js
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if (!root) return []
const ans = []
// 双数组
let curLevel = [root]
let nextLevel = []
while (curLevel.length > 0) {
let tmp = []
while (curLevel.length > 0) {
const cur = curLevel.shift()
tmp.push(cur.val)
if (cur.left) nextLevel.push(cur.left)
if (cur.right) nextLevel.push(cur.right)
}
ans.push(tmp)
curLevel = nextLevel
nextLevel = []
}
return ans
};层序，二叉树最大宽度
【做法1】:
- 利用哈希表统计每个节点的层数。即：在将节点加入队列时记录该节点的层数。
- 每弹出一个节点时，判断该节点是否在当前层，如果不是，说明已经进入下一层了，此时可以统计上一层的节点数。
【做法2】:
- 做法 1 中的哈希表存储了很多冗余信息。当你进入下一层时，“上一层节点所对应的层数”这个信息就是不需要的了。
- 我们统计的是最大层数，并且我们是从第一层走到最后一层的，所以我们真正需要的存储的只有当前层的节点数量和当前最大宽度。
【做法2具体实现】:
- 利用三个变量代替哈希表。这三个变量分别记录
- 当前层的最后一个节点
curEnd - 下一层的最后一个节点
nextEnd - 当前层的节点数量
curNodes
- 当前层的最后一个节点
- 初始时，
curEnd为头节点nextEnd为空curNodes为 0，因为头节点还未弹出，所以第一层还未统计完。
- 队列弹出一个节点时，将他的子节点加入到队列中。
- 每添加一个子节点时，都要更新
nextEnd为该子节点。 - 由于我们是层序遍历，所以最终的
nextEnd值就是下一层的最后一个节点。
- 每添加一个子节点时，都要更新
- 弹出一个节点时，判断该节点是否是
curEnd节点。- 如果不是，说明该节点还在当前层，当前层节点数量 + 1
- 如果是，说明当前层节点数统计统计完毕。此时可以进行一些收尾工作：
- 更新最大宽度
- 更新下一层的最后一个节点
- 重置下下一层的最后一个节点
py
def binary_tree_max_width1(root):
max_w = 0 # 最大宽度
if root is None:
return max_w
queue = Queue()
queue.put(root)
level_map = {} # 存储每个节点所在的层数
level_map[root] = 1 # root 的层数是第一层
store_level = 1 # 记录弹出元素前位于第几层
store_w = 0 # 统计当前层宽度。 弹出元素时加 1
while not queue.empty():
cur = queue.get()
if store_level == level_map[cur]:
# 还在同一层, 宽度(节点数)加1
store_w += 1
else:
# 弹出元素层级和记录的层级不同, 说明当前循环已经进去下一层
store_level += 1
max_w = max(store_w, max_w)
store_w = 1 # 新一层的第一个元素已经弹出
# 前面代码能成立的条件是, 通过 map 同理了每个节点的层数
if cur.left is not None:
# 在将新节点加到队列中时, 存储该节点的对应层数; 该节点的层数等于其父节点的层数+1
level_map[cur.left] = level_map[cur] + 1
queue.put(cur.left)
if cur.right is not None:
level_map[cur.right] = level_map[cur] + 1
queue.put(cur.right)
# 遍历完最后一层后, 再"结算"一下。
max_w = max(store_w, max_w)
return max_wpy
def binary_tree_max_width2(root):
max_w = 0
if root is None:
return max_w
queue = Queue() # 利用队列实现层级遍历
queue.put(root) # 队列初始值为根节点。 后续通过判断队列是否为空来退出循环
cur_end = root # 当前层的最后节点
next_end = None # 下一层的最后节点
cur_w = 0 # 当前层节点数量
while not queue.empty(): # 队列为空, 则遍历完毕
# 每次都弹出一个元素
cur = queue.get()
cur_w += 1
# 弹出一个元素的同时, 按从左到右的次序依次将子节点放入队列中
if cur.left is not None:
next_end = cur.left # 下一层的最后节点在加入子节点的过程中产出, 谁留到最后谁就是下层最后节点
queue.put(cur.left)
if cur.right is not None:
next_end = cur.right
queue.put(cur.right)
# 判断弹出的元素是否是当前层最后节点
if cur is cur_end:
# 如果是, 则整理当前层信息
max_w = max(max_w, cur_w)
# 同时准备下一层信息
cur_w = 0
cur_end = next_end
next_end = None
return max_w衍生话题
根据前序和中序的遍历结果，如何确定一个二叉树
根据前序遍历结果，可以确定一个根节点。 根据中序遍历结果和一个根节点，可以确定左右两棵子树。 对两棵子树再次按照相同的方法继续确定根节点。 依次递推则可确定一棵二叉树。