二叉树总结

基本概念

二叉树最重要的概念应该是：前序遍历、中序遍历、后续遍历 了。

• 前序遍历：根节点->左子树->右子树（根->左->右）
• 中序遍历：左子树->根节点->右子树（左->根->右）
• 后序遍历：左子树->右子树->根节点（左->右->根）
• 层序遍历: 从上至下、从左至右层次进行，借助队列实现。

对应实现代码为：

def traverse(root):
    if root is None:
        return root
    
    # 前序位置
    traverse(root.left)
    # 中序位置
    traverse(root.right)
    # 后续位置
    
    

实现手段

1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

无论使用哪种思维模式，你都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

(这段话的出处: https://labuladong.github.io/algo/2/21/36/)

常见题型

树的深度

典型问题：111. 二叉树的最小深度

首先考虑，使用遍历是否可以做呢。可以的，使用前序遍历，统计每个叶子节点的深度，取 min 即可。

也可以采用递归的思想，当前节点的最小深度是左子树和右子树中深度较小的一颗的高度 + 1的结果。

class Solution:
    
    def minDepth2(self, root: Optional[TreeNode]) -> int:
        # 遍历
        global depth, res
        res = math.inf  # 记录最终深度结果
        depth = 0  # 记录当前循环中深度的结果
        
        def traverse(root: Optional[TreeNode]):
            global depth, res
            if root is None:
                return 0
            depth += 1
            if root.left is None and root.right is None:
                # 叶子节点
                res = min(res, depth)
            traverse(root.left)
            traverse(root.right)
            
            depth -= 1
            
            return res
        
        return traverse(root)
    
    def minDepth(self, root: Optional[TreeNode]) -> int:
        # 分解问题，当前节点的深度等于左右节点的深度之和
        if root is None:
            return 0
        left_depth = self.minDepth(root.left)
        right_depth = self.minDepth(root.right)
        
        if left_depth == 0:
            return right_depth + 1
        elif right_depth == 0:
            return left_depth + 1
        else:
            return min(left_depth, right_depth) + 1

根据遍历结果构造树

前序遍历和后续遍历都可以提供 root 节点的位置(首位或者是尾位)，中序遍历可以通过 root 节点的位置分割出左子树和右子树，进而迭代完成树的构建。如果要获得唯一的树结构， 中序遍历是必须的。

比如题目105. 从前序与中序遍历序列构造二叉树

from typing import List, Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# leetcode submit region begin(Prohibit modification and deletion)

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        
        if len(preorder) == 0:
            return None
        
        root_node = TreeNode(preorder[0])
        if len(preorder) == 1:
            return root_node
        
        root_pos = -1
        for idx, value in enumerate(inorder):
            if value == preorder[0]:
                root_pos = idx
        
        root_node.left = self.buildTree(preorder[1:1 + root_pos], inorder[0:root_pos])
        root_node.right = self.buildTree(preorder[1 + root_pos:], inorder[root_pos + 1:])
        
        return root_node


# leetcode submit region end(Prohibit modification and deletion)


if __name__ == "__main__":
    preorder = [3, 9, 20, 15, 7]
    inorder = [9, 3, 15, 20, 7]
    solution = Solution()
    res = solution.buildTree(preorder, inorder)
    print(res.val)

以及106. 从中序与后序遍历序列构造二叉树

from typing import List, Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if len(postorder) == 0:
            return
        
        if len(postorder) == 1:
            return TreeNode(postorder[-1])
        
        root_node = TreeNode(postorder[-1])
        
        # 找出 root_value 的在 inorder 的位置
        idx = 0
        for idx, value in enumerate(inorder):
            if value == postorder[-1]:
                break
        root_node.left = self.buildTree(inorder[:idx], postorder[:idx])
        root_node.right = self.buildTree(inorder[idx + 1:], postorder[idx:-1])
        
        return root_node


# leetcode submit region end(Prohibit modification and deletion)

if __name__ == "__main__":
    inorder = [9, 3, 15, 20, 7]
    postorder = [9, 15, 7, 20, 3]
    solution = Solution()
    res = solution.buildTree(inorder, postorder)
    print(res.val)

在做这类题的时候，边界的处理是比较关键的，可以先写好左子树是什么、右子树是什么，然后写代码来实现。

公共祖先问题

比如题目 236. 二叉树的最近公共祖先

存在两种情况：

• p 和 q 的公共节点不为 q 或者 p；
• p 和 q 的公共节点为 p 或者 q；

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# leetcode submit region begin(Prohibit modification and deletion)

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None:
            return None
        # 前序遍历的过程中，没找到 lca，但先遇到了 q 或者 p。
        if root.val == p.val or root.val == q.val:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        if left is not None and right is not None:
            # 认为是 lca 点
            return root
        
        # 兼容了均为 None 的情况
        if left is not None:
            return left
        else:
            return right
        
# leetcode submit region end(Prohibit modification and deletion)


if __name__ == "__main__":
    node1 = TreeNode(1)
    node2 = TreeNode(2)
    node3 = TreeNode(3)
    node4 = TreeNode(4)
    node5 = TreeNode(5)
    
    node1.left = node2
    node1.right = node3
    node3.left = node4
    node3.right = node5

结合前序遍历和后续遍历，分别考虑上述所说的两种情况：

• q 和 p 为分开的两个节点，左子树和右子树都会返回非 None 的结果，返回 root 。
• q 和 p 有祖先关系，那么在遍历的过程中，就会先遇到 q 和 p，返回 root 会被最终带出去。

序列化和反序列化

如题目297. 二叉树的序列化与反序列化 和 652. 寻找重复的子树

前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。

那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

序列化

from typing import List, Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:
    
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        res = []
        self.pre_order(root, res)
        return ",".join(res)
    
    def pre_order(self, root, res):
        if not root:
            res.append("null")
            return
        
        res.append(str(root.val))
        self.pre_order(root.left, res)
        self.pre_order(root.right, res)
    
    def bfs(self, res: List) -> Optional[TreeNode]:
        val = res.pop(0)
        if val == 'null':
            return None
        root = TreeNode(val)
        root.left = self.bfs(res)
        root.right = self.bfs(res)
        
        return root
    
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        return self.bfs(data.split(','))


# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))
# leetcode submit region end(Prohibit modification and deletion)

可以使用前序遍历来实现二叉树的序列化，增加 null 用于识别叶子节点。比较有趣的是，借助 bfs 实现了前序遍历构造树。

但对于问题 652. 寻找重复的子树，对于每个节点，进行树的序列化，验证序列化的结果是否有重复，就可以记录下重复的子树。

但不能使用前序遍历了，前序遍历不能让当前节点知道子树的形状。需要利用到后序遍历，才能构造完整的序列化树。

# leetcode submit region begin(Prohibit modification and deletion)
# 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 __init__(self):
        self.res = []
        self.sub_tree_str_count = {}
    
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        self.traverse(root)
        return self.res
    
    def traverse(self, root: Optional[TreeNode]):
        if not root:
            return "#"
        
        left = self.traverse(root.left)
        right = self.traverse(root.right)
        
        sub_tree_str = left + "," + right + "," + str(root.val)
        
        if sub_tree_str not in self.sub_tree_str_count:
            self.sub_tree_str_count[sub_tree_str] = 1
        else:
            self.sub_tree_str_count[sub_tree_str] += 1
        
        # 避免重复加入树
        if self.sub_tree_str_count[sub_tree_str] == 2:
            self.res.append(root)
        
        return sub_tree_str


# leetcode submit region end(Prohibit modification and deletion)

参考

东哥手把手带你刷二叉树（第一期）

东哥手把手带你刷二叉树（第二期）

东哥手把手带你刷二叉树（第三期）