8. 二叉树

约 6762 字大约 23 分钟

LeetcodePythonC++

2026-01-08

8. 二叉树

8.1 二叉树的中序遍历

94. 二叉树的中序遍历

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

示例 1：

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

示例 2：

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

示例 3：

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

提示

思路：递归迭代左子树，存储根节点，递归迭代右子树即可。

Python

class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    def dfs(node: Optional[TreeNode]) -> None:
        if node is None:
            return
        dfs(node.left)       # 左
        ans.append(node.val) # 根（这行代码移到前面就是前序，移到后面就是后序）
        dfs(node.right)      # 右

    ans = []
    dfs(root)
    return ans

C++

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
    vector<int> res;
public:
    void dfs(TreeNode *root) {
        if (root == nullptr) {
            return;
        }
        dfs(root->left);
        res.push_back(root->val);
        dfs(root->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }
};

时间复杂度：所有操作均为 $O(1)$ 。

空间复杂度： $O(min(p,capacity))$ ，其中 p 为 put 的调用次数。

8.2 二叉树的最大深度

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

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

示例 2：

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

提示

思路：递归。

Python

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

C++

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
// 自底向上
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int left_deep = maxDepth(root->left);
        int right_deep = maxDepth(root->right);
        return max(left_deep, right_deep) + 1;
    }
};

C++

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
// 自顶向下
class Solution {
    int max_deep = 0;
public:
    void dfs(TreeNode *root, int cur_deep) {
        if (root == nullptr) {
            max_deep = max(max_deep, cur_deep);
            return;
        }
        cur_deep++;
        dfs(root->left, cur_deep);
        dfs(root->right, cur_deep);
    }
    int maxDepth(TreeNode* root) {
        dfs(root, 0);
        return max_deep;
    }
};

时间复杂度： $O(n)$ ，其中 n 为二叉树的节点个数。

空间复杂度： $O(n)$ 。最坏情况下，二叉树退化成一条链，递归需要 $O(n)$ 的栈空间。

8.3 翻转二叉树

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

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

示例 3：

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

提示

思路：递归。

Python

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 = right  # 交换左右儿子
    root.right = left
    return root

C++

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:

    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return root;
        }
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

时间复杂度： $O(n)$ ，其中 n 为二叉树的节点个数。

空间复杂度： $O(n)$ 。最坏情况下，二叉树退化成一条链，递归需要 $O(n)$ 的栈空间。

8.4 对称二叉树

101. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

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

示例 2：

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

提示

思路：如果当前节点有一个孩子为空，那么左右孩子都要为空。如果全不为空，那么左孩子的右孩子要和右孩子的左孩子相等，反之，左孩子的左孩子要和右孩子的右孩子相等，才说明对称。

Python

class Solution:
# 100. 相同的树（改成镜像判断）
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)

C++

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
    bool fun(TreeNode *p, TreeNode *q) {
        if (p == nullptr || q == nullptr) {
            return p == q;
        }
        return p->val == q->val && fun(p->left, q->right) && fun(p->right, q->left);
    }
    bool isSymmetric(TreeNode* root) {
        return fun(root->left, root->right);
    }
};

时间复杂度： $O(n)$ ，其中 n 为二叉树的节点个数。

空间复杂度： $O(n)$ 。最坏情况下，二叉树退化成一条链，递归需要 $O(n)$ 的栈空间。

8.5 二叉树的直径

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的长度由它们之间边数表示。

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

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

提示

思路：设计一个递归函数，每次递归中计算我们的最大直径是否需要更新，当前节点的最大直径等于左子树的最大直径和右子树的最大直径中的最大值再加2（默认左右结点都存在，如果是空节点不存在要返回-1），按照这个算法，叶子节点需要返回0，那么它的左右孩子也就是空节点时需要返回-1，这样返回值 return max(-1, -1) + 1 才能正好让叶子的直径为0。

Python

class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
    ans = 0
    def dfs(node: Optional[TreeNode]) -> int:
        if node is None:
            return -1  # 对于叶子来说，链长就是 -1+1=0
        l_len = dfs(node.left) + 1  # 左子树最大链长+1
        r_len = dfs(node.right) + 1  # 右子树最大链长+1
        nonlocal ans
        ans = max(ans, l_len + r_len)  # 两条链拼成路径
        return max(l_len, r_len)  # 当前子树最大链长
    dfs(root)
    return ans

C++

/**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    * };
    */
class Solution {
private:
    int res = 0;
public:
    int fun(TreeNode *root) {
        if (root == nullptr) {
            return -1;
        }
        int max_left = fun(root->left);
        int max_right = fun(root->right);
        res = max(res, max_left + max_right + 2);
        return max(max_left, max_right) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        fun(root);
        return res;
    }
};

时间复杂度： $O(n)$ ，其中 n 为二叉树的节点个数。

空间复杂度： $O(n)$ 。最坏情况下，二叉树退化成一条链，递归需要 $O(n)$ 的栈空间。

8.6 二叉树的层序遍历

102. 二叉树的层序遍历

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

示例 1：

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

示例 2：

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

示例 3：

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

提示

思路：用一个队列来保存一层的信息，遍历每一层时，此时队列里的长度就是这层的结点数，也就是循环次数；循环时，获取队列头节点并出列，将该节点的节点值加入数组，将左右结点加入队列（如果有）。

Python

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

C++

/**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    * };
    */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        vector<vector<int>> res;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            vector<int> vals;
            int n = q.size();
            while (n--) {
                TreeNode *t = q.front();
                q.pop();
                vals.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            res.push_back(vals);
        }
        return res;

    }
};

时间复杂度： $O(n)$ ，其中 n 为二叉树的节点个数。虽然写了个二重循环，但每个节点只会入队出队各一次，所以总的循环次数是节点个数之和，即 O(n)。

空间复杂度： $O(n)$ 。满二叉树（每一层都填满）最后一层有大约 n/2 个节点，因此队列中最多有 $O(n)$ 个元素，所以空间复杂度是 $O(n)$ 的。

8.7 将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示

思路：二叉树一定要先看能不能转化成子问题，这样就可以用递归简化代码。给定一个数组，转换成二叉搜索树，先确定其中间节点为根节点，那么数组左侧就是转换成二叉搜索树的子问题，右侧同理，这可以用递归解决。

Python

class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
    if not nums:
        return None
    m = len(nums) // 2
    left = self.sortedArrayToBST(nums[:m])
    right = self.sortedArrayToBST(nums[m + 1:])
    return TreeNode(nums[m], left, right)

C++

/**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    * };
    */
class Solution {
public:
    TreeNode *dfs(vector<int>& nums, int left, int right) {
        if (left == right) {
            return nullptr;
        }
        int m = (left + right) / 2;
        return new TreeNode(nums[m], dfs(nums, left, m), dfs(nums, m + 1, right));
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return dfs(nums, 0, nums.size());
    }
};

空间复杂度： $O(n)$ 。满二叉树（每一层都填满）最后一层有大约 n/2 个节点，因此队列中最多有 $O(n)$ 个元素，所以空间复杂度是 $O(n)$ 的。

8.8 验证二叉搜索树

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下：节点的左子树只包含严格小于当前节点的数。节点的右子树只包含严格大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

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

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示

思路：dfs 额外传入两个参数，分别表示从根到当前节点路径上的最小值和最大值。当前节点的值必须在最小值和最大值之间（不能等于）。

Python

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)

C++

/**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    * };
    */
class Solution {
public:
    bool isValidBST(TreeNode* root, long long left, long long right) {
        if (root == nullptr) {
            return true;
        }
        int x = root->val;
        return left < x && x < right && isValidBST(root->left, left, x) && isValidBST(root->right, x, right);
    }
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, LLONG_MIN, LLONG_MAX);
    }
};

时间复杂度： $O(n)$ ，其中 n 为二叉搜索树的节点个数。

空间复杂度： $O(n)$ 。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 $O(n)$ 的栈空间。

8.9 二叉搜索树中第 K 小的元素

230. 二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。

示例 1：

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

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3。

提示

思路：既然是搜索树，那么中序遍历就对应了升序数组，直接返回索引为k-1的元素即可。

Python

class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
    ans = 0
    def dfs(node: Optional[TreeNode]) -> None:
        nonlocal k, ans
        if node is None or k <= 0:
            return
        dfs(node.left)  # 左
        k -= 1
        if k == 0:
            ans = node.val  # 根
        dfs(node.right)  # 右
    dfs(root)
    return ans

C++

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
    vector<int> res;
public:
    void dfs(TreeNode *root) {
        if (root == nullptr) {
            return;
        }
        dfs(root->left);
        res.push_back(root->val);
        dfs(root->right);
    }
    int kthSmallest(TreeNode* root, int k) {
        dfs(root);
        return res[k - 1];
    }
};

时间复杂度： $O(n)$ ，其中 n 是二叉树的大小（节点个数）。

空间复杂度： $O(h)$ ，其中 h 是树高，递归需要 $O(h)$ 的栈空间。最坏情况下树是一条链，h=n，空间复杂度为 $O(n)$ 。

8.10 二叉树的右视图

199. 二叉树的右视图

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：

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

示例 2：

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

提示

思路：很容易想到用层序遍历来保存每一层的信息，然后取出每一层的最右侧即可。优化：只保存每一层的最后一个元素，可以少一次遍历。

Python

class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    if root is None:
        return []
    ans = []
    cur = [root]
    while cur:
        ans.append(cur[-1].val)
        nxt = []
        for node in cur:
            if node.left:  nxt.append(node.left)
            if node.right: nxt.append(node.right)
        cur = nxt
    return ans

C++

/**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    * };
    */
class Solution { // 直接复用层序遍历
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        if (root == nullptr) {
            return {};
        }
        vector<vector<int>> level;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            vector<int> vals;
            while (n--) {
                TreeNode *t = q.front();
                q.pop();
                vals.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            level.push_back(vals);
        }
        return level;
    }
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        vector<vector<int>> level;
        level = levelOrder(root);
        for (auto v : level) {
            res.push_back(v.back());
        }
        return res;
    }
};

C++

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution { // 只获取层序遍历最后一个元素，少一次遍历和 vector，推荐
public:
    vector<int> rightSideView(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        vector<int> res;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            res.push_back(q.back()->val);
            while (n--) {
                TreeNode *t = q.front();
                q.pop();
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }
        return res;
    }
};

时间复杂度： $O(n)$ ，其中 n 为二叉树的节点个数。虽然写了个二重循环，但每个节点只会添加到列表中一次，所以总的循环次数是节点个数之和，即 $O(n)$ 。

空间复杂度： $O(n)$ 。满二叉树（每一层都填满）最后一层有大约 n/2 个节点，因此节点数组中最多有 $O(n)$ 个元素，所以空间复杂度是 $O(n)$ 的。

8.11 二叉树展开为链表

114. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树先序遍历顺序相同。

示例 1：

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

示例 2：

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

示例 3：

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

提示

思路：依然是递归，需要确定的是访问顺序，根据得到的链表是先序遍历，也就是根左右，那么我们使用头插法反向构造，可以确定是右-左-根的顺序；具体操作的时候，深度递归可以找到第一个节点，让当前根的左孩子为空，右孩子指向头部，当前根节点变为下一次插入的头部。

Python

class Solution:
head = None

def flatten(self, root: Optional[TreeNode]) -> None:
    if root is None:
        return
    self.flatten(root.right)
    self.flatten(root.left)
    root.left = None
    root.right = self.head  # 头插法，相当于链表的 root.next = head
    self.head = root  # 现在链表头节点是 root

C++

* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
    TreeNode *head;
public:

    void flatten(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        flatten(root->right);
        flatten(root->left);
        root->left = nullptr;
        root->right = head;
        head = root;
    }
};

时间复杂度： $O(n)$ ，其中 n 是二叉树的节点个数。

空间复杂度： $O(n)$ 。递归需要 $O(n)$ 的栈空间。

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

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]

提示

思路：依然是递归，通过 preorder 可以确定根节点的位置，inorder 中找到根节点的位置减去起点就可以得知左子树的大小，进而变成一个原问题的子问题。

Python

class Solution:
head = None

def flatten(self, root: Optional[TreeNode]) -> None:
    if root is None:
        return
    self.flatten(root.right)
    self.flatten(root.left)
    root.left = None
    root.right = self.head  # 头插法，相当于链表的 root.next = head
    self.head = root  # 现在链表头节点是 root

C++

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0) {
            return nullptr;
        }
        int left_size = ranges::find(inorder, preorder[0]) - inorder.begin();
        vector<int> pre1(preorder.begin() + 1, preorder.begin() + 1 + left_size);
        vector<int> pre2(preorder.begin() + 1 + left_size, preorder.end());
        vector<int> in1(inorder.begin(), inorder.begin() + left_size);
        vector<int> in2(inorder.begin() + left_size + 1, inorder.end());
        return new TreeNode(preorder[0], buildTree(pre1, in1), buildTree(pre2, in2));
    }
};

C++

class Solution {
// 用 span 可以避免拷贝
TreeNode* build(span<int> preorder, span<int> inorder) {
    if (preorder.empty()) { // 空节点
        return nullptr;
    }
    int left_size = ranges::find(inorder, preorder[0]) - inorder.begin(); // 左子树的大小
    TreeNode* left = build(preorder.subspan(1, left_size), inorder.subspan(0, left_size));
    TreeNode* right = build(preorder.subspan(1 + left_size), inorder.subspan(1 + left_size));
    return new TreeNode(preorder[0], left, right);
}

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, inorder);
    }
};

时间复杂度： $O(n^2)$ ，其中 n 为 preorder 的长度。最坏情况下二叉树是一条链，我们需要递归 $O(n)$ 次，每次都需要 $O(n)$ 的时间查找 preorder[0] 和复制数组。

空间复杂度： $O(n^2)$ 。

重要

优化：用一个哈希表来存储数组的值对应的下标，可以避免一直遍历带来的时间开销，用 $O(n)$ 的空间来换取时间。

Python

class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    index = {x: i for i, x in enumerate(inorder)}

    def dfs(pre_l: int, pre_r: int, in_l: int) -> Optional[TreeNode]:
        if pre_l == pre_r:  # 空节点
            return None
        left_size = index[preorder[pre_l]] - in_l  # 左子树的大小
        left = dfs(pre_l + 1, pre_l + 1 + left_size, in_l)
        right = dfs(pre_l + 1 + left_size, pre_r, in_l + 1 + left_size)
        return TreeNode(preorder[pre_l], left, right)

    return dfs(0, len(preorder), 0)  # 左闭右开区间

C++

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        unordered_map<int, int> index;
        for (int i = 0; i < n; i++) {
            index[inorder[i]] = i;
        }

        auto dfs = [&](this auto&& dfs, int pre_l, int pre_r, int in_l) -> TreeNode* {
            if (pre_l == pre_r) { // 空节点
                return nullptr;
            }
            int left_size = index[preorder[pre_l]] - in_l; // 左子树的大小
            TreeNode* left = dfs(pre_l + 1, pre_l + 1 + left_size, in_l);
            TreeNode* right = dfs(pre_l + 1 + left_size, pre_r, in_l + 1 + left_size);
            return new TreeNode(preorder[pre_l], left, right);
        };
        return dfs(0, n, 0); // 左闭右开区间
    }
};

时间复杂度： $O(n)$ ，其中 n 为 preorder 的长度。递归 $O(n)$ 次，每次只需要 $O(1)$ 的时间。

空间复杂度： $O(n)$ 。

注：由于哈希表常数比数组大，实际运行效率可能不如写法一。

8.13 路径总和 III

437. 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示

思路：把每一个根到叶子的路径看成一条链表，就可以转换成和为k的子数组。用 s 存储从根访问当当前节点的总和，比如 10-5-2-1 这条路径，在节点1时，s 为 18，targetSum 为8，18 - 8 = 10，如果哈希表中存在 10 就说明结果 res 可以加一，因此每次遍历要把当前节点的值加入哈希表。注意访问完左右分支要在哈希表删掉当前节点，比如从10-5切换到10- -3，要删除15这个key。

Python

class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
    # key：从根到 node 的节点值之和
    # value：节点值之和的出现次数
    # 注意在递归过程中，哈希表只保存根到 node 的路径的前缀的节点值之和
    cnt = defaultdict(int)  
    cnt[0] = 1
    ans = 0

    # s 表示从根到 node 的父节点的节点值之和（node 的节点值尚未计入）
    def dfs(node: Optional[TreeNode], s: int) -> None:
        if node is None:
            return

        nonlocal ans
        s += node.val
        # 把 node 当作路径的终点，统计有多少个起点
        ans += cnt[s - targetSum]

        cnt[s] += 1
        dfs(node.left, s)
        dfs(node.right, s)
        cnt[s] -= 1  # 恢复现场（撤销 cnt[s] += 1）

    dfs(root, 0)
    return ans

C++

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
    int res = 0;
    unordered_map<long long, int> cnt = {{0, 1}};
public:
    void dfs(TreeNode *root, long long s, int targetSum) {
        if (root == nullptr) {
            return ;
        }
        s += root->val;
        res += cnt[s - targetSum];
        cnt[s]++;
        dfs(root->left, s, targetSum);
        dfs(root->right, s, targetSum);
        cnt[s]--;
    }
    int pathSum(TreeNode* root, int targetSum) {
        dfs(root, 0, targetSum);
        return res;
    }
};

时间复杂度： $O(n)$ ，其中 n 是二叉树的节点个数。

空间复杂度： $O(n)$ 。

8.14 二叉树的最近公共祖先

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

提示

思路：递归的返回条件要么是空，要么是找到p和q了，如果递归的左右子树分别找到了p和q，那么当前的根节点就是最近公共祖先。如果p和q在一个分支怎么办？比如q在p的下面，这时遇到上面的p就返回了，而p的兄弟又是空，因此会直接返回p，p就是最近公共祖先。

Python

class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if root in (None, p, q):  # 找到 p 或 q 就不往下递归了，原因见上面答疑
        return root
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    if left and right:  # 左右都找到
        return root  # 当前节点是最近公共祖先
    # 如果只有左子树找到，就返回左子树的返回值
    # 如果只有右子树找到，就返回右子树的返回值
    # 如果左右子树都没有找到，就返回 None（注意此时 right = None）
    return left or right

C++

/**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    * };
    */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || 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;
    }
};

时间复杂度： $O(n)$ ，其中 n 是二叉树的节点个数。

空间复杂度： $O(n)$ 。