二叉树

LeetCode 958 https://leetcode.cn/problems/check-completeness-of-a-binary-tree/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 层序遍历二叉树。如果遍历到了一个非空节点之前遍历过空节点，就不是完全二叉树。 时间复杂度：O(N)，其中 N 是树节点个数。 空间复杂度：O(N)。 ...

LeetCode 297 https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题可以使用前序遍历或者层序遍历，这里使用层序遍历。 在序列化时需要注意空节点也需要保存。在反序列化时，为了分割字符串，使用了 stringstream。 getline(ss, token, ',') 序列化和反序列化的时空复杂度相同。 时间复杂度：O(n)。 空间复杂度：O(n)。 ...

LeetCode 226 https://leetcode.cn/problems/invert-binary-tree/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 递归调用 invertTree(root.left)，获取到左子树翻转后的结果 left。 递归调用 invertTree(root.right)，获取到右子树翻转后的结果 right。 交换左右儿子，即更新 root.left 为 right，更新 root.right 为 left。 返回 root。 递归边界：如果 root 是空节点，返回空。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...

LeetCode 112 https://leetcode.cn/problems/path-sum/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 直接递归调用 hasPathSum，当前节点为叶子节点时判断是否存在路径。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...

LeetCode 662 https://leetcode.cn/problems/maximum-width-of-binary-tree/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 这道题类似二叉树层序遍历，但是除了要保留节点本身，还需要保留节点在本层的编号。对节点 i，左儿子为 2 * i，右儿子为 2 * i + 1。 另外，由于最大 3000 个节点，如果是一条只有右儿子的链，那么编号会达到 \(2^3000\)，任何数据类型都会溢出，所以我们需要使用 unsigned long long 类型，当溢出后会重新回到 0，而不会报错。 时间复杂度：O(n)，其中 n 是二叉树的节点个数。需要遍历所有节点。 空间复杂度：O(n)。广度优先搜索的空间复杂度最多为 O(n)。 ...

LeetCode 113 https://leetcode.cn/problems/path-sum-ii/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 子集型回溯。 时间复杂度：\(O(n^2)\)，其中 n 是二叉树的节点个数。对于「一条链 + 完全二叉树」这样的「扫帚型」二叉树，我们会在 O(n) 个叶子节点处，都去复制长为 O(n) 的 path，所以总的时间复杂度为 \(O(n^2)\)。 空间复杂度：O(n)。返回值不计入。 ...

LeetCode 98 https://leetcode.cn/problems/validate-binary-search-tree/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 使用中序遍历验证二叉搜索树，比较当前节点与上一个节点的值的大小。需要注意的是，为了处理节点值为 INT_MIN 的情况，pre 需要初始化为 LLONG_MIN。 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。 ...

LeetCode 110 https://leetcode.cn/problems/balanced-binary-tree/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 这道题对 LeetCode 104 二叉树的最大深度 稍加改造，当求出左右子树的深度时，如果深度差超过 1，则返回 -1，父节点如果接收到 -1，也直接返回 -1，否则返回当前子树的深度。最后判断根节点得到的深度是否为 -1。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...

LeetCode 144 https://leetcode.cn/problems/binary-tree-preorder-traversal/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 递归求二叉树的前序遍历。 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。 ...

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) 的栈空间。 ...