递归

LeetCode 572 https://leetcode.cn/problems/subtree-of-another-tree/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 如果暴力匹配，时间复杂度是 O(n⋅min(n,m))，如何改进呢？ 定义节点 node 的高度为 node 到其最深叶子的路径上的节点个数。特别地，叶子的高度为 1。设 subRoot 的高度为 hs。 设 node 为 root 中的节点。我们可以在匹配之前，先判断 node 的高度是否等于 hs，只有在相等时才做匹配。 这样做的时间复杂度是多少呢？ 首先，对于 root 中的两个高度相同的节点 p 和 q（p  =q），不可能出现 p 是 q 的祖先，或者 q 是 p 的祖先。因为如果 p 是 q 的祖先，那么 p 的高度必然大于 q 的高度，反之亦然。 其次，对于 root 中的两个高度相同的节点 p 和 q（p != q），子树 p 和子树 q 没有任何交集。假如有交集，说明从 p 出发可以到达某个点 node，从 q 出发也可以到达 node，但这只有在 p 是 q 的祖先，或者 q 是 p 的祖先时才成立，与两个节点高度相同矛盾。 所以，root 中的所有与 hs 高度相同的节点，对应的子树两两不相交，这些子树的节点个数之和不超过 n，所以总的匹配次数也不会超过 n，下面代码中的 dfs 的时间复杂度为 O(n)。 时间复杂度：O(n+m)，其中 n 是二叉树 root 的节点个数，m 是二叉树 subRoot 的节点个数。注意当 subRoot 的节点个数比 n 还要多时，dfs 并不会遍历 subRoot 中的所有节点。其中 O(m) 是计算 subRoot 树高的时间，如果限制 getHeight 递归访问的节点个数至多为 n，则可以做到 O(n) 的时间复杂度。 空间复杂度：O(n+m)。如果限制 getHeight 递归访问的节点个数至多为 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 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) 的栈空间。 ...

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)\)。 ...