二叉树

LeetCode 104 https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 递归求最大深度。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...

LeetCode 101 https://leetcode.cn/problems/symmetric-tree/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 与 LeetCode 100 相同的树 类似，这个比较 p 的左子树和 q 和右子树。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...

LeetCode 129 https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 使用参数记录路径之和，当当前节点为叶子节点时更新答案，并处理节点为空的情况。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...

LeetCode 105 https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题使用递归从二叉树的前序和中序遍历构造二叉树。首先找到中序遍历中根节点的位置，它左边就是左子树的长度。然后构造左右子树的前序和中序遍历，递归调用，构造二叉树。 时间复杂度：\(O(n^2)\)，其中 n 为 preorder 的长度。最坏情况下二叉树是一条链，我们需要递归 O(n) 次，每次都需要 O(n) 的时间查找 preorder[0] 和复制数组。 空间复杂度：\(O(n^2)\)。 ...

LeetCode 94 https://leetcode.cn/problems/binary-tree-inorder-traversal/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 二叉树中序遍历的递归实现。 时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。 空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。 ...

LeetCode 199 https://leetcode.cn/problems/binary-tree-right-side-view/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 先递归右子树，再递归左子树，当某个深度首次到达时，对应的节点就在右视图中。 时间复杂度：O(n)，其中 n 是二叉树的节点个数。 空间复杂度：O(h)，其中 h 是二叉树的高度。递归需要 O(h) 的栈空间。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...

LeetCode 103 https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 这道题类似 LeetCode 102，只是需要判断当前层的奇偶性，如果是偶数，需要把当前层的结果翻转后再加入答案。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。满二叉树（每一层都填满）最后一层有大约 n/2 个节点，因此数组中最多有 O(n) 个元素，所以空间复杂度是 O(n) 的。 ...

LeetCode 236 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 二叉树题目。如果当前节点为空，或者为 p，或者为 q，直接返回当前节点。 如果左右子树都找到 p 或 q，返回当前节点。 如果左子树找到 p 和 q，返回左子树的结果。 如果右子树找到 p 和 q，返回右子树的结果。 如果左右子树都没找到，返回空节点。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树是一条链，因此递归需要 O(n) 的栈空间。 ...

LeetCode 102 https://leetcode.cn/problems/binary-tree-level-order-traversal/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 这道题是 BFS 的经典题目。本题使用两个数组 cur 和 nxt 来实现 BFS。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。满二叉树（每一层都填满）最后一层有大约 n/2 个节点，因此数组中最多有 O(n) 个元素，所以空间复杂度是 O(n) 的。 ...