2022-02-21 二叉树递归专题

二叉树的遍历

首先需要明确：前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点，绝不仅仅是三个顺序不同的 List：

• 前序位置的代码在刚刚进入一个二叉树节点的时候执行；
• 后序位置的代码在将要离开一个二叉树节点的时候执行；
• 中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。

前中后序「位置」，就是常说的前中后序「遍历」有所区别：可以在前序位置写代码往一个 List 里面塞元素，那最后可以得到前序遍历结果；但并不是说你就不可以写更复杂的代码做更复杂的事。

二叉树遍历参考资料

简单对比“遍历方式”与“位置”的联系：

• 前序遍历算法：

// 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
List<Integer> preorderTraverse(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    if (root == null) {
        return res;
    }
    // 前序遍历的结果，root.val 在第一个
    res.add(root.val);
    // 利用函数定义，后面接着左子树的前序遍历结果
    res.addAll(preorderTraverse(root.left));
    // 利用函数定义，最后接着右子树的前序遍历结果
    res.addAll(preorderTraverse(root.right));
}

• 中序遍历算法

List<Integer> preorderTraverse(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    if (root == null) {
        return res;
    }
    res.addAll(preorderTraverse(root.left));
   // 中序遍历
    res.add(root.val);
    res.addAll(preorderTraverse(root.right));
}

• 后续遍历算法

List<Integer> preorderTraverse(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    if (root == null) {
        return res;
    }
    res.addAll(preorderTraverse(root.left));
    res.addAll(preorderTraverse(root.right));
    // 后序遍历
    res.add(root.val);
}

• 二叉树的特殊遍历：层次遍历，层序遍历属于迭代遍历

// 输入一棵二叉树的根节点，层序遍历这棵二叉树
void levelTraverse(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    // 从上到下遍历二叉树的每一层
    while (!q.isEmpty()) {
        int sz = q.size();
        // 从左到右遍历每一层的每个节点
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            // 将下一层节点放入队列
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
    }
}

这里面 while 循环和 for 循环分别从上到下和从左到右的遍历：

遍历的几种常用方式

• 递归
• BFS
• DFS

二叉树基础练习

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

题解：前序遍历

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        self.queue = []
        self.prev(root)

        return self.queue


    def prev(self, node):
        if not node:
            return

        self.queue.append(node.val)
        self.prev(node.left)
        self.prev(node.right)

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

题解：

# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        self.queue = []
        self.middle(root)

        return self.queue


    def middle(self, node):
        if not node:
            return
        self.middle(node.left)
        self.queue.append(node.val)
        self.middle(node.right)

145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

题解：

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        self.queue = []
        self.post(root)

        return self.queue

    def post(self, node):
        if not node:
            return
        self.post(node.left)
        self.post(node.right)
        self.queue.append(node.val)

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

题解：

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        self.queue = []
        self.ans = []

        self.queue.append(root)
        self.ans.append([root.val])

        while self.queue:
            temp = []
            for _ in range(len(self.queue)):
                node = self.queue.pop(0)
                if node.left:
                    self.queue.append(node.left)
                    temp.append(node.left.val)
                if node.right:
                    self.queue.append(node.right)
                    temp.append(node.right.val)
            if temp:
                self.ans.append(temp)

        return self.ans

107. 二叉树的层序遍历 II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

题解：对比层次遍历

# 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 levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        self.queue = [root]
        self.ans = [[root.val]]

        while self.queue:
            temp = []
            for _ in range(len(self.queue)):
                node = self.queue.pop(0)
                if node.left:
                    self.queue.append(node.left)
                    temp.append(node.left.val)
                if node.right:
                    self.queue.append(node.right)
                    temp.append(node.right.val)

            if temp:
                self.ans.insert(0, temp)

        return self.ans

103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100

分析：锯齿层次遍历相对于层次遍历可以引入一个标志位来控制每层的遍历顺序即可

题解：

# 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 zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        self.queue = []
        self.ans = []
        self.flag = True

        self.queue.append(root)
        self.ans.append([root.val])

        while self.queue:
            temp = []
            self.flag = not self.flag
            
            for _ in range(len(self.queue)):
                node = self.queue.pop(0)
                if node.left:
                    temp.append(node.left.val)
                    self.queue.append(node.left)
                if node.right:
                    temp.append(node.right.val)
                    self.queue.append(node.right)
            
            if not self.flag:
                temp = temp[::-1]

            if temp:
                
                self.ans.append(temp)

        return self.ans

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列

题解：

-------------------------------------------------------------------------

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

题解：

• 递归

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)

        return max(left, right) + 1

• BFS：仔细观察这里的BFS就是二叉树的层次遍历

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0

        queue = []
        queue.append(root)
        ans = 0
        while queue:
            ans += 1
            for _ in range(len(queue)):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)
            
        return ans

• DFS：DFS算法需要利用我们常说的遍历顺序：前序，中序，后序

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0

        self.ans = 0
        self._dfs(root, 0)
        return self.ans

    def _dfs(self, node, level):
        if not node:
            return
        
        if self.ans < level + 1:
            self.ans = level + 1
        
        self._dfs(node.left, level + 1)
        self._dfs(node.right, level + 1)

总结：对于一个二叉树的遍历问题，一般都会有递归，广度优先搜索（BFS）和深度优先搜索（DFS）

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :

给定二叉树

          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

题解：

# 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 diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.result = 0
        self.deep(root)
        return self.result
        
    def deep(self, root):
        if not root:
            return -1

        left = self.deep(root.left) + 1 if root.left else 0
        right = self.deep(root.right) + 1 if root.right else 0

        self.result = max(left + right, self.result)

        return max(left, right)