8. 二叉树新

约 4206 字大约 14 分钟

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:
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.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 { // 只保留层序遍历最后一个元素，少一次遍历
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();
            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);
            }
            res.push_back(vals.back());
        }
        return res;
    }
};

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

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

8. 二叉树 新

8. 二叉树新