二叉树

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

LeetCode 662 https://leetcode.cn/problems/maximum-width-of-binary-tree/description/ 难度：中等 这道题类似二叉树层序遍历，但是除了要保留节点本身，还需要保留节点在本层的编号。对节点 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/ 难度：中等 子集型回溯。 时间复杂度：\(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/ 难度：中等 使用中序遍历验证二叉搜索树，比较当前节点与上一个节点的值的大小。需要注意的是，为了处理节点值为 INT_MIN 的情况，pre 需要初始化为 LLONG_MIN。 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。 ...

LeetCode 110 https://leetcode.cn/problems/balanced-binary-tree/description/ 难度：简单 这道题对 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/ 难度：简单 递归求二叉树的前序遍历。 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。 ...

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

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

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

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