算法题刷题笔记-二叉树

1. 二叉树基础：

一些概念：

满二叉树：深度为k的满二叉树必须满足节点总数为$2^k-1$，且第i层的节点数达到最大值$2^{i-1}$
完全二叉树：所有非最后一层节点均有两个子节点，且最后一层节点连续集中在左侧。（从上到下，从左到右，结点编号连续）
二叉搜索树：左子树的所有节点都小于中间节点，右子树的所有节点都大于中间节点。（搜索一个节点的时间复杂度是logn）
平衡二叉搜索树：左子树和右子树的高度差的绝对值不大于1。（map、set、multimap和multiset的底层数据结构都是平衡二叉搜索树，它们插入或检索一个元素的时间复杂度都是logn；unordered_map和unordered_set底层是哈希表）

储存方式：

链式存储：二叉链表，每个节点类一般有三个对象（left，val和right），分别对应的是该节点的左孩子节点、节点值和右孩子节点。

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

线性存储：数组，元素i的左孩子节点下标是2i+1，右孩子节点下标是2i+2

遍历方式：

DFS和BFS：前中后序遍历是DFS，层序遍历是BFS；方法可以是队列递归或队列迭代
前中后序主要是看根节点访问的先后次序：前序是中左右，中序是左中右，后序是左右中

2. 二叉树的中序遍历（LC94）

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def dfs(root):
            if not root:
                return

            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
        dfs(root)
        return res

最基础的中序遍历，遍历顺序是左中右。

3. 二叉树的最大深度（LC104）

自顶向下 - 前序遍历
自底向上 - 后序遍历

自底向上比较反直觉，但很符合递归写法

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # 自底向上 -> 后序遍历左右中
        # 终止条件
        if root is None:
            return 0
        # 左子树高度
        left_height = self.maxDepth(root.left)
        # 右子树高度
        right_height = self.maxDepth(root.right)
        # 中间节点处理逻辑
        return 1 + max(left_height, right_height)

自顶向下符合构造二叉树的直觉（从根节点出发），但写法较复杂。(附灵神题解)

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node: Optional[TreeNode], depth: int) -> int:
            if node is None:
                return
            depth += 1
            nonlocal ans
            ans = max(ans, depth)
            dfs(node.left, depth)
            dfs(node.right, depth)
        dfs(root, 0)
        return ans

其实是走了一遍前序遍历，在dfs的过程中逐步累加深度depth，并通过比较更新最大深度ans。（注意nonlocal的使用）

4. 二叉树的最小深度（LC111）

与最大深度不同，需要特别考虑左右子树为空的情况：左子树为空时，只取右子树+1；右子树为空时，只取左子树+1.
左右都不为空时，取左右子树最小值+1

主体思想不变，还是自底向上的后序遍历法

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        if root.right is None:
            return 1 + self.minDepth(root.left)
        if root.left is None:
            return 1 + self.minDepth(root.right)
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

贴一下灵神的自顶向下方法，明显麻烦太多了。还要考虑一个优化剪枝（当递归中发现cnt ≥ ans，由于继续向下递归也不会让ans变小，直接返回。）

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        ans = inf
        def dfs(node: Optional[TreeNode], cnt: int) -> None:
            if node is None:
                return
            nonlocal ans
            cnt += 1
            if cnt >= ans:
                return  # 最优性剪枝
            if node.left is node.right:  # node 是叶子
                ans = cnt
                return
            dfs(node.left, cnt)
            dfs(node.right, cnt)
        dfs(root, 0)
        return ans if root else 0

5. 翻转二叉树（LC226）

可以采用前序和后序，但中序不行

后序遍历

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        # 后序遍历
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left, root.right = root.right, root.left
        return root

前序遍历

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        root.left, root.right = root.right, root.left  # 交换左右儿子
        self.invertTree(root.left)  # 翻转左子树
        self.invertTree(root.right)  # 翻转右子树
        return root

6. 二叉树的层序遍历（LC102）

前中后序遍历是DFS，层序遍历是BFS

队列思想，保存每一层的遍历节点

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans = []
        q = deque([root])
        while q:
            vals = []
            for _ in range(len(q)):
                node = q.popleft()
                vals.append(node.val)
                if node.left:  q.append(node.left)
                if node.right: q.append(node.right)
            ans.append(vals)
        return ans