六、基础算法精讲：二叉树与递归

一、深入理解

1.1 二叉树的最大深度

Leetcode 104

非全局变量写法

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None: return 0
        l_depth = self.maxDepth(root.left)
        r_depth = self.maxDepth(root.right)
        return max(l_depth, r_depth) + 1
1
2
3
4
5
6

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        int l_depth = maxDepth(root->left);
        int r_depth = maxDepth(root->right);
        return max(l_depth, r_depth) + 1;
    }
};
1
2
3
4
5
6
7
8
9

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

全局变量写法

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        ans = 0
        
        def dfs(node, cnt):
            if node is None:
                return
            cnt += 1
            nonlocal ans
            ans = max(ans, cnt)
            dfs(node.left, cnt)
            dfs(node.right, cnt)
        
        dfs(root, 0)
        
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    int ans = 0;

    void dfs(TreeNode *node, int cnt) {
        if (!node) return;
        cnt += 1;
        ans = max(ans, cnt);
        dfs(node->left, cnt);
        dfs(node->right, cnt);
    }

public:
    int maxDepth(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

二、灵活应用

2.1 相同的树

Leetcode 100

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
1
2
3
4
5

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p || !q) return p == q;
        return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};
1
2
3
4
5
6
7

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

2.2 对称的二叉树

Leetcode 101

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q
        return p.val == q.val and self.isSameTree(p.left, q.right) and self.isSameTree(p.right, q.left)

    def isSymmetric(self, root: Optional[TreeNode])->bool:
        return self.isSameTree(root.left, root.right)
1
2
3
4
5
6
7
8

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if (!p || !q) return p == q;
        return p->val == q->val && isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return isSameTree(root->left, root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

2.3 平衡二叉树

Leetcode 110

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_height(node: Optional[TreeNode])->int:
            if node is None: return 0
            left_h = get_height(node.left)
            if left_h == -1: return -1
            right_h = get_height(node.right)
            if right_h == -1 or abs(left_h - right_h) > 1: return -1
            return max(left_h, right_h) + 1
        return get_height(root) != -1
1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    int get_height(TreeNode *root) {
        if (!root) return 0;
        int left_depth = get_height(root->left);
        if (left_depth == -1) return -1;
        int right_depth = get_height(root->right);
        if (right_depth == -1 || abs(right_depth - left_depth) > 1) return -1;
        return max(left_depth, right_depth) + 1;
    }

    bool isBalanced(TreeNode* root) {
        return get_height(root) != -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

2.4 二叉树的右视图

Leetcode 199

当递归深度等于答案 $ans$ 的长度时，将该结点记录到 $ans$ 中。

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def dfs(node: Optional[TreeNode], depth: int)->None:
            if node is None: return
            if depth == len(ans):
                ans.append(node.val)
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
        dfs(root, 0)
        return ans
1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    vector<int> ans;

    void dfs(TreeNode *node, int depth) {
        if (!node) return;
        if (depth == ans.size())
            ans.push_back(node->val);
        dfs(node->right, depth + 1);
        dfs(node->left, depth + 1);
    }

    vector<int> rightSideView(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

2.5 节点与其祖先之间的最大差值

Leetcode 1026

思路一：从上到下，递归中的【递】

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node: Optional[TreeNode], mn: int, mx: int)->None:
            if node is None: return
            mn = min(mn, node.val)
            mx = max(mx, node.val)
            nonlocal ans
            ans = max(ans, node.val - mn, mx - node.val)
            dfs(node.left, mn, mx)
            dfs(node.right, mn, mx)
        dfs(root, root.val, root.val)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int ans = 0;
    void dfs(TreeNode *node, int mn, int mx) {
        if (!node) return;
        mn = min(mn, node->val);
        mx = max(mx, node->val);
        ans = max(ans, max(node->val - mn, mx - node->val));
        dfs(node->left, mn, mx);
        dfs(node->right, mn, mx);
    }

    int maxAncestorDiff(TreeNode* root) {
        dfs(root, root->val, root->val);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

针对思路一的一点优化

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node: Optional[TreeNode], mn: int, mx: int)->None:
            if node is None: 
                nonlocal ans
                ans = max(ans, mx - mn)
                return
            mn = min(mn, node.val)
            mx = max(mx, node.val)
            dfs(node.left, mn, mx)
            dfs(node.right, mn, mx)
        dfs(root, root.val, root.val)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int ans = 0;
    void dfs(TreeNode *node, int mn, int mx) {
        if (!node) {
            ans = max(ans, mx - mn);
            return;
        }
        mn = min(mn, node->val);
        mx = max(mx, node->val);
        dfs(node->left, mn, mx);
        dfs(node->right, mn, mx);
    }

    int maxAncestorDiff(TreeNode* root) {
        dfs(root, root->val, root->val);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

思路二：递归中的【归】

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node: Optional[TreeNode])->(int, int) :
            if node is None:
                return inf, -inf
            mn = mx = node.val
            l_mn, l_mx = dfs(node.left)
            r_mn, r_mx = dfs(node.right)
            mn = min(mn, l_mn, r_mn)
            mx = max(mx, l_mx, r_mx)
            nonlocal ans
            ans = max(ans, node.val - mn, mx - node.val)
            return mn, mx
        dfs(root)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int ans = 0;

    pair<int, int> dfs(TreeNode *node) {
        if (!node) return {INT_MAX, INT_MIN};
        int mn = node->val, mx = node->val;
        auto [l_mn, l_mx] = dfs(node->left);
        auto [r_mn, r_mx] = dfs(node->right);
        mn = min(mn, min(l_mn, r_mn));
        mx = max(mx, max(l_mx, r_mx));
        ans = max(ans, max(node->val - mn, mx - node->val));
        return {mn, mx};
    }

    int maxAncestorDiff(TreeNode* root) {
        dfs(root);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

2.6 根到叶路径上的不足节点

Leetcode 1080

class Solution:
    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
        limit -= root.val
        if root.left is root.right:
            return None if limit > 0 else root
        if root.left: root.left = self.sufficientSubset(root.left, limit)
        if root.right: root.right = self.sufficientSubset(root.right, limit)
        return root if root.left or root.right else None
1
2
3
4
5
6
7
8

class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        limit -= root->val;
        if (root->left == root->right)
            return limit > 0 ? nullptr : root;
        if (root->left) root->left = sufficientSubset(root->left, limit);
        if (root->right) root->right = sufficientSubset(root->right, limit);
        return root->left || root->right ? root: nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

2.7 删点成林

Leetcode 1110

class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        ans = []
        s = set(to_delete)
        def dfs(node: Optional[TreeNode])->Optional[TreeNode]:
            if node is None: return None
            node.left = dfs(node.left)
            node.right = dfs(node.right)
            if node.val not in s: return node
            if node.left: ans.append(node.left)
            if node.right: ans.append(node.right)
            return None
        if dfs(root): ans.append(root)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    vector<TreeNode*> ans;
    unordered_set<int> s;

    TreeNode *dfs(TreeNode *node) {
        if (!node) return nullptr;
        node->left = dfs(node->left);
        node->right = dfs(node->right);
        if (!s.count(node->val)) return node;
        if (node->left) ans.push_back(node->left);
        if (node->right) ans.push_back(node->right);
        return nullptr;
    }

    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        for (int x: to_delete) s.insert(x);
        if (dfs(root)) ans.push_back(root);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

三、前序/中序/后序

3.1 验证二叉搜索树

Leetcode 98

前序遍历

$left$ 和 $right$ 分别代表当前节点子树值的范围（开区间）。

class Solution:
    def isValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool:
        if root is None:
            return True
        x = root.val
        return left < x < right and \
               self.isValidBST(root.left, left, x) and \
               self.isValidBST(root.right, x, right)
1
2
3
4
5
6
7
8

class Solution {
public:
    bool isValidBST(TreeNode* root, long left = LONG_MIN, long right = LONG_MAX) {
        if (!root) return true;
        long x = root->val;
        return left < x && x < right &&
               isValidBST(root->left, left, x) && 
               isValidBST(root->right, x, right);
    }
};
1
2
3
4
5
6
7
8
9
10

中序遍历

中序遍历二叉搜索树后一定会得到一个递增的数组！

class Solution:
    pre = -inf
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        if not self.isValidBST(root.left) or root.val <= self.pre:
            return False
        self.pre = root.val
        return self.isValidBST(root.right)
1
2
3
4
5
6
7
8
9

class Solution {
    long pre = LONG_MIN;
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        if (!isValidBST(root->left) || root->val <= pre) return false;
        pre = root->val;
        return isValidBST(root->right);
    }
};
1
2
3
4
5
6
7
8
9
10

后序遍历

先遍历左右子树，再判断节点值，即当前节点大于左子树区间的最大值，小于右子树区间的最小值，将区间往上传。

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node: Optional[TreeNode])->Tuple:
            if node is None: return inf, -inf
            l_min, l_max = dfs(node.left)
            r_min, r_max = dfs(node.right)
            x = node.val
            if x <= l_max or x >= r_min:
                return -inf, inf
            return min(l_min, x), max(r_max, x)
        return dfs(root)[1] != inf
1
2
3
4
5
6
7
8
9
10
11

class Solution {
    pair<long, long> dfs(TreeNode *node) {
        if (!node) return {LONG_MAX, LONG_MIN};
        auto[l_min, l_max] = dfs(node->left);
        auto[r_min, r_max] = dfs(node->right);
        long x = node->val;
        if (x <= l_max || x >= r_min) return {LONG_MIN, LONG_MAX};
        return {min(l_min, x), max(r_max, x)};
    }

public:
    bool isValidBST(TreeNode* root) {
        return dfs(root).second != LONG_MAX;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

四、最近公共祖先

4.1 二叉树的最近公共祖先

Leetcode 236

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root in (None, p, q):
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left or right
1
2
3
4
5
6
7
8
9

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if (left && right) return root;
        return left ? left : right;
    }
};
1
2
3
4
5
6
7
8
9
10

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

4.2 二叉搜索树的最近公共祖先

Leetcode 235

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        x = root.val
        if p.val < x and q.val < x:
            return self.lowestCommonAncestor(root.left, p, q)
        if p.val > x and q.val > x:
            return self.lowestCommonAncestor(root.right, p, q)
        return root
1
2
3
4
5
6
7
8

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int x= root->val;
        if (p->val < x && q->val < x)
            return lowestCommonAncestor(root->left, p, q);
        if (p->val > x && q->val > x)
            return lowestCommonAncestor(root->right, p, q);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

4.3 最深叶子节点的最近公共祖先

Leetcode 1123、Leetcode 865

解法一：递归

class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        ans = None
        max_depth = -1
        def dfs(node: Optional[TreeNode], depth: int)->int:
            nonlocal ans, max_depth
            if node is None:
                max_depth = max(max_depth, depth)
                return depth
            left_max_depth = dfs(node.left, depth + 1)
            right_max_depth = dfs(node.right, depth + 1)
            if left_max_depth == right_max_depth == max_depth:
                ans = node
            return max(left_max_depth, right_max_depth)
        dfs(root, 0)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        TreeNode *ans = nullptr;
        int max_depth = -1;
        function<int(TreeNode*, int)> dfs = [&](TreeNode *node, int depth) {
            if (node == nullptr) {
                max_depth = max(max_depth, depth);
                return depth;
            }
            int left_max_depth = dfs(node->left, depth + 1);
            int right_max_depth = dfs(node->right, depth + 1);
            if (left_max_depth == right_max_depth && left_max_depth == max_depth)
                ans = node;
            return max(left_max_depth, right_max_depth);
        };
        dfs(root, 0);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

解法二：自底向上

class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        def dfs(node: Optional[TreeNode])->(int, Optional[TreeNode]):
            if node is None:
                return 0, None
            left_height, left_lca = dfs(node.left)
            right_height, right_lca = dfs(node.right)
            if left_height > right_height:
                return left_height + 1, left_lca
            if left_height < right_height:
                return right_height + 1, right_lca
            return left_height + 1, node
        return dfs(root)[1]
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    pair<int, TreeNode*> dfs(TreeNode *node) {
        if (node == nullptr) return {0, nullptr};
        auto [left_height, left_lca] = dfs(node->left);
        auto [right_height, right_lca] = dfs(node->right);
        if (left_height > right_height)
            return {left_height + 1, left_lca};
        if (left_height < right_height)
            return {right_height + 1, right_lca};
        return {left_height + 1, node};
    }

public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).second;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

五、BFS

5.1 二叉树的层序遍历

Leetcode 102

解法一：两个数组

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans = []
        cur = [root]
        while cur:
            nxt, vals = [], []
            for node in cur:
                vals.append(node.val)
                if node.left: nxt.append(node.left)
                if node.right: nxt.append(node.right)
            cur = nxt
            ans.append(vals)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> ans;
        vector<TreeNode*> cur = {root};
        while (cur.size()) {
            vector<TreeNode*> nxt;
            vector<int> vals;
            for (auto node: cur) {
                vals.push_back(node->val);
                if (node->left) nxt.push_back(node->left);
                if (node->right) nxt.push_back(node->right);
            }
            cur = move(nxt);
            ans.emplace_back(vals);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

解法二：一个队列

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            vector<int> vals;
            for (int n = q.size(); n -- ; ) {
                auto node = q.front();
                q.pop();
                vals.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ans.emplace_back(vals);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5.2 二叉树的锯齿形层序遍历

Leetcode 103

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans = []
        q = deque([root])
        even = False
        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[::-1] if even else vals)
            even = not even
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.push(root);
        for (bool even = false; !q.empty(); even = !even) {
            vector<int> vals;
            for (int n = q.size(); n -- ; ) {
                auto node = q.front();
                q.pop();
                vals.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            if (even) reverse(vals.begin(), vals.end());
            ans.emplace_back(vals);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5.3 找树左下角的值

Leetcode 513

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        while q:
            node = q.popleft()
            if node.right: q.append(node.right)
            if node.left: q.append(node.left)
        return node.val
1
2
3
4
5
6
7
8

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        TreeNode* node;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            node = q.front(); q.pop();
            if (node->right) q.push(node->right);
            if (node->left) q.push(node->left);
        }
        return node->val;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5.4 填充每个节点的下一个右侧节点指针

Leetcode 116

解法一：DFS

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        pre = []
        def dfs(node: 'Node', depth: int)->None:
            if node is None:
                return 
            if depth == len(pre):
                pre.append(node)
            else:
                pre[depth].next = node
                pre[depth] = node
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
        dfs(root, 0)
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    vector<Node *> pre;

public:
    Node* connect(Node* root) {
        dfs(root, 0);
        return root;
    }

    void dfs(Node *node, int depth) {
        if (!node) return;
        if (depth == pre.size()) pre.push_back(node);
        else {
            pre[depth]->next = node;
            pre[depth] = node;
        }
        dfs(node->left, depth + 1);
        dfs(node->right, depth + 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 时间复杂度：$O(n)$
• 空间复杂度：$O(h)$

解法二：BFS

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if root is None:
            return None
        q = [root]
        while q:
            for x, y in pairwise(q):
                x.next = y
            tmp = q
            q = []
            for node in tmp:
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return nullptr;
        vector<Node*> q = {root};
        while (!q.empty()) {
            vector<Node*> nxt;
            for (int i = 0; i < q.size(); i ++ ) {
                Node *node = q[i];
                if (i) q[i - 1]->next = node;
                if (node->left) nxt.push_back(node->left);
                if (node->right) nxt.push_back(node->right);
            }
            q = move(nxt);
        }   
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

解法三：BFS + 链表

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        cur = root
        while cur:
            nxt = dummy = ListNode()
            while cur:
                if cur.left:
                    nxt.next = cur.left
                    nxt = cur.left
                if cur.right:
                    nxt.next = cur.right
                    nxt = cur.right
                cur = cur.next
            cur = dummy.next
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    Node* connect(Node* root) {
        Node *dummy = new Node();
        Node *cur = root;
        while (cur) {
            dummy->next = nullptr;
            Node *nxt = dummy;
            while (cur) {
                if (cur->left) {
                    nxt->next = cur->left;
                    nxt = cur->left;
                }
                if (cur->right) {
                    nxt->next = cur->right;
                    nxt = cur->right;
                }
                cur = cur->next;
            }
            cur = dummy->next;
        }
        delete dummy;
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

5.5 反转二叉树的奇数层

Leetcode 2415

解法一：BFS

class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        q, level = [root], 0
        while q[0].left:
            q = list(chain.from_iterable((node.left, node.right) for node in q))
            if level == 0:
                for i in range(len(q) // 2):
                    x, y = q[i], q[len(q) - 1 - i]
                    x.val, y.val = y.val, x.val
            level ^= 1
        return root
1
2
3
4
5
6
7
8
9
10
11

解法二：DFS

class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node1: Optional[TreeNode], node2: Optional[TreeNode], is_odd_level: bool)->None:
            if node1 is None:
                return
            if is_odd_level: node1.val, node2.val = node2.val, node1.val
            dfs(node1.left, node2.right, not is_odd_level)
            dfs(node1.right, node2.left, not is_odd_level)
        dfs(root.left, root.right, True)
        return root
1
2
3
4
5
6
7
8
9
10

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5.6 二叉树的堂兄弟节点 II

Leetcode 2641

class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        root.val = 0
        q = [root]
        while q:
            tmp = q
            q = []
            next_level_sum = 0
            for node in tmp:
                if node.left:
                    q.append(node.left)
                    next_level_sum += node.left.val
                if node.right:
                    q.append(node.right)
                    next_level_sum += node.right.val
            for node in tmp:
                children_sum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)
                if node.left: node.left.val = next_level_sum - children_sum
                if node.right: node.right.val = next_level_sum - children_sum
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    TreeNode* replaceValueInTree(TreeNode* root) {
        root->val = 0;
        vector<TreeNode*> q = {root};
        while (!q.empty()) {
            vector<TreeNode*> nxt;
            int nxt_level_sum = 0;
            for (auto node: q) {
                if (node->left) {
                    nxt.push_back(node->left);
                    nxt_level_sum += node->left->val;
                }
                if (node->right) {
                    nxt.push_back(node->right);
                    nxt_level_sum += node->right->val;
                }
            }
            for (auto node: q) {
                int children_sum = (node->left ? node->left->val : 0) + (node->right ? node->right->val : 0);
                if (node->left) node->left->val = nxt_level_sum - children_sum;
                if (node->right) node->right->val = nxt_level_sum - children_sum;
            }
            q = move(nxt);
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$