每日算法一练：剑指offer——树篇（4）

1.计算二叉树的深度

某公司架构以二叉树形式记录，请返回该公司的层级数。

示例 1：

输入：root = [1, 2, 2, 3, null, null, 5, 4, null, null, 4]
输出: 4
解释: 上面示例中的二叉树的最大深度是 4，沿着路径 1 -> 2 -> 3 -> 4 或 1 -> 2 -> 5 -> 4 到达叶节点的最长路径上有 4 个节点。

方法一：后序遍历（DFS）

算法解析

• 特点：后序遍历是深度优先搜索的一种实现方式，在递归中先计算子树的深度，再计算当前树的深度。
• 关键点：
  1. 每个节点的深度等于其左子树深度和右子树深度中的较大值 + 1。
  2. 利用递归实现。

步骤

1. 终止条件：如果当前节点 root 为空，则返回深度 0。
2. 递归计算：
   • 计算当前节点左子树的深度，calculateDepth(root.left)。
   • 计算当前节点右子树的深度，calculateDepth(root.right)。
3. 返回值：
   • 返回当前节点深度，即 max(左子树深度, 右子树深度) + 1。

Java代码

class Solution {public int calculateDepth(TreeNode root) {if (root == null) {return 0; // 如果节点为空，深度为0}// 递归计算左、右子树的深度，取较大值加1return Math.max(calculateDepth(root.left), calculateDepth(root.right)) + 1;}
}

复杂度分析

• 时间复杂度：O(N)，每个节点仅被访问一次。
• 空间复杂度：O(N)，最差情况下（退化为链表），递归栈的深度为 N。

方法二：层序遍历（BFS）

算法解析

• 特点：层序遍历是广度优先搜索的一种实现方式，通过逐层遍历计算树的深度。
• 关键点：
  1. 每遍历一层时，计数器 res 增加 1。
  2. 通过队列存储当前层的所有节点，依次将下一层节点加入队列。

步骤

1. 初始化：
   • 队列 queue 存储根节点。
   • 深度计数器 res 初始化为 0。
2. 循环遍历：
   • 每次遍历队列中的所有节点，将它们的子节点加入一个临时队列 tmp。
   • 将临时队列赋值给 queue，表示更新为下一层节点。
   • 深度计数器 res 自增。
3. 终止条件：当队列为空时，说明所有节点都已遍历完成，返回深度计数器。

Java代码

class Solution {public int calculateDepth(TreeNode root) {if (root == null) {return 0; // 如果节点为空，深度为0}// 递归计算左、右子树的深度，取较大值加1return Math.max(calculateDepth(root.left), calculateDepth(root.right)) + 1;}
}

复杂度分析

• 时间复杂度：O(N)，每个节点仅被访问一次。
• 空间复杂度：O(N)，最差情况下（完全平衡树），队列中最多同时存储 N/2 个节点。

两种方法对比

方法	适用场景	优缺点
DFS	递归计算，适合理解树的递归性质。	代码简洁，递归深度受栈空间限制，可能导致栈溢出。
BFS	遍历树的所有层，计算深度或查找某一层内容。	使用队列实现，较耗内存，但避免了递归深度的限制。

选择建议

• 如果树的节点较少，DFS 和 BFS 都适合。
• 如果树的节点较多且深度较大，建议使用 BFS，以避免递归导致的栈溢出问题。

2.判断是否为平衡二叉树

        输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:

输入：root = [3,9,20,null,null,15,7]
输出：true 
解释：如下图

示例 2:

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
解释：如下图

提示：

• 0 <= 树的结点个数 <= 10000

解题思路解析

        题目要求判断一棵二叉树是否是平衡二叉树，所谓平衡二叉树的定义是：任意节点的左右子树深度之差不超过1。

基于此，可以通过两种方式实现：

1. 后序遍历 + 剪枝（从底至顶判断）
2. 先序遍历 + 深度判断（从顶至底判断）

方法一：后序遍历 + 剪枝

核心思路

        利用后序遍历的方式计算子树深度，同时在递归过程中判断当前子树是否平衡。如果发现某个子树不平衡，立即返回，减少无效计算。

算法步骤

1. 定义一个递归函数 recur(root)，用于返回当前节点的子树深度：
   • 如果当前节点为 null，返回深度为 0；
   • 递归求左右子树的深度 left 和 right；
   • 如果左右子树已经被标记为不平衡（深度为 -1），则直接返回 -1；
   • 如果左右子树深度差大于 1，也返回 -1；
   • 否则，返回当前节点的深度，即 max(left, right) + 1。
2. 在主函数 isBalanced(root) 中调用 recur(root)，判断返回值是否为 -1。如果是，则说明树不平衡，返回 false；否则返回 true。

代码实现（Java）

class Solution {public boolean isBalanced(TreeNode root) {return recur(root) != -1;}private int recur(TreeNode root) {if (root == null) return 0; // 叶子节点高度为 0int left = recur(root.left);  // 左子树高度if (left == -1) return -1;   // 左子树不平衡，直接剪枝int right = recur(root.right); // 右子树高度if (right == -1) return -1;  // 右子树不平衡，直接剪枝return Math.abs(left - right) <= 1 ? Math.max(left, right) + 1 : -1; // 判断当前节点是否平衡}
}

复杂度分析

• 时间复杂度：
  每个节点最多访问一次，因此时间复杂度为 O(N)，其中 NNN 是节点总数。
• 空间复杂度：
  系统递归栈的深度取决于树的高度，最坏情况下（树退化为链表）空间复杂度为 O(N)。

方法二：先序遍历 + 深度判断

核心思路

        通过一个辅助函数 depth(root) 计算当前节点的深度，并在主函数中递归判断每个节点是否满足平衡条件。若任一节点不满足条件，则标记整棵树不平衡。

算法步骤

1. 定义辅助函数 depth(root)，用于计算树的深度：
   • 若节点为 null，返回深度 0；
   • 否则递归计算左右子树深度，返回 max(left, right) + 1。
2. 主函数 isBalanced(root)：
   • 若根节点为 null，直接返回 true；
   • 通过 depth(root.left) 和 depth(root.right) 计算左右子树深度，判断是否满足平衡条件：abs(left - right) <= 1；
   • 同时递归判断左右子树是否平衡。
3. 只有当所有节点均满足条件时，返回 true。

代码实现（Java）

class Solution {public boolean isBalanced(TreeNode root) {if (root == null) return true; // 空树是平衡的return Math.abs(depth(root.left) - depth(root.right)) <= 1 // 当前节点平衡&& isBalanced(root.left) // 左子树平衡&& isBalanced(root.right); // 右子树平衡}private int depth(TreeNode root) {if (root == null) return 0; // 空节点深度为 0return Math.max(depth(root.left), depth(root.right)) + 1; // 递归计算深度}
}

复杂度分析

• 时间复杂度：
  • 最坏情况（满二叉树）：每个节点都需要调用 depth 计算子树深度，每次计算需遍历整个子树，导致时间复杂度为 O(Nlog⁡N)。
  • 最优情况（剪枝效果明显）：当某子树不平衡时提前结束计算，降低时间复杂度。
• 空间复杂度：
  同方法一，递归栈深度为树的高度，最坏情况下为 O(N)。

方法对比

方法	时间复杂度	空间复杂度	适用场景
后序遍历 + 剪枝	O(N)	O(N)	效率优先
先序遍历 + 判断	O(Nlog⁡N)	O(N)	思路简单易懂

3.二叉搜索树的最近公共祖先

        给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点2和节点4的最近公共祖先是2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉搜索树中。

这是关于在 二叉搜索树（BST） 中寻找两个节点最近公共祖先（LCA）的经典题目。以下是思路的详细解析和实现过程：

核心概念：

1. 祖先的定义：
   如果节点 p 是节点 root 的左子树或右子树中的节点，或者 p == root，则称 root 是 p 的祖先。

2. 最近公共祖先的定义：
   节点 root 是 p 和 q 的公共祖先，并且 root 是离 p 和 q 最近的那个祖先。根据这一定义，最近公共祖先可能有以下三种情况：

   • p 和 q 分别位于 root 的左右子树中。
   • p == root 且 q 在 root 的子树中。
   • q == root 且 p 在 root 的子树中。

二叉搜索树的性质：

• 对于任意节点 root：
  • 若 p.val 和 q.val 都小于 root.val，说明它们都在左子树。
  • 若 p.val 和 q.val 都大于 root.val，说明它们都在右子树。
  • 否则，root 就是最近公共祖先。

方法一：迭代

思路：

1. 从根节点 root 开始遍历。
2. 根据 p 和 q 的值相对于 root.val 的大小关系决定遍历方向：
   • 如果 p 和 q 都在右子树中，进入右子树。
   • 如果 p 和 q 都在左子树中，进入左子树。
   • 否则，当前节点就是最近公共祖先。
3. 返回找到的 root。

优化：

通过保证 p.val < q.val，可以减少判断条件。

代码（优化版）：

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (p.val > q.val) { // 确保 p.val < q.valTreeNode temp = p;p = q;q = temp;}while (root != null) {if (root.val < p.val) { // p, q 都在右子树root = root.right;} else if (root.val > q.val) { // p, q 都在左子树root = root.left;} else {break; // 找到最近公共祖先}}return root;}
}

方法二：递归

思路：

1. 对于当前节点 root，判断 p 和 q 的值：
   • 如果 p 和 q 都小于 root，递归左子树。
   • 如果 p 和 q 都大于 root，递归右子树。
   • 否则，当前节点就是最近公共祖先。
2. 返回找到的 root。

代码：

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root.val < p.val && root.val < q.val) {return lowestCommonAncestor(root.right, p, q);}if (root.val > p.val && root.val > q.val) {return lowestCommonAncestor(root.left, p, q);}return root; // root 是最近公共祖先}
}

复杂度分析：

1. 时间复杂度：
   • 最好情况：树是平衡的，树高为 log⁡N，每次递归或迭代排除一半子树，复杂度为 O(log⁡N)。
   • 最坏情况：树退化成链表，复杂度为 O(N)。
2. 空间复杂度：
   • 迭代：O(1)，无需额外空间。
   • 递归：最差情况下递归深度为 O(N)。

4.二叉树的最近公共祖先

解题思路

定义

1. 祖先：若节点 ppp 在节点 rootrootroot 的子树中，或 p=rootp = rootp=root，则称 rootrootroot 是 ppp 的祖先。
2. 最近公共祖先：设节点 rootrootroot 为节点 p,qp, qp,q 的某公共祖先，若其左子节点 root.leftroot.leftroot.left 和右子节点 root.rightroot.rightroot.right 都不是 p,qp, qp,q 的公共祖先，则称 rootrootroot 为“最近公共祖先”。

思路概述

我们通过递归遍历的方式来解决：

• 当递归到底部时返回 null。
• 如果当前节点是 ppp 或 qqq，直接返回当前节点。
• 对当前节点的左右子树分别递归，返回值记为 leftleftleft 和 rightrightright。
• 根据 leftleftleft 和 rightrightright 的情况判断当前节点是否是最近公共祖先。

具体判断

1. 终止条件：

   • 当前节点 rootrootroot 为 null，直接返回 null。
   • 当前节点等于 ppp 或 qqq，直接返回 rootrootroot。

2. 递推逻辑：

   • 对左子树递归调用，返回值为 leftleftleft。
   • 对右子树递归调用，返回值为 rightrightright。

3. 返回值分析：

   • 情况 1：left=nullleft = nullleft=null 且 right=nullright = nullright=null，说明当前节点的左右子树都不包含 p,qp, qp,q，返回 null。
   • 情况 2：left≠nullleft \neq nullleft=null 且 right≠nullright \neq nullright=null，说明 ppp 和 qqq 分别位于当前节点的左右子树，当前节点为最近公共祖先，返回 rootrootroot。
   • 情况 3：left=nullleft = nullleft=null 且 right≠nullright \neq nullright=null，说明 p,qp, qp,q 均在右子树中，返回 rightrightright。
   • 情况 4：left≠nullleft \neq nullleft=null 且 right=nullright = nullright=null，说明 p,qp, qp,q 均在左子树中，返回 leftleftleft。

代码实现

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 终止条件if (root == null || root == p || root == q) return root;// 递归左右子树TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);// 根据返回值判断if (left == null && right == null) return null; // 情况 1if (left != null && right != null) return root; // 情况 2return left != null ? left : right; // 情况 3 和 情况 4}
}

复杂度分析

1. 时间复杂度：O(N)O(N)O(N)
   • 每个节点最多被访问一次，因此时间复杂度为树中节点总数 NNN。
2. 空间复杂度：O(N)O(N)O(N)
   • 在最坏情况下，递归调用栈的深度等于树的高度，最差情况下（链状树）高度为 NNN。

示例分析

输入

二叉树：

      3/ \5   1/ \ / \6  2 0  8/ \7   4

查找节点 5 和 1 的最近公共祖先。

输出

最近公共祖先是 3，因为 5 和 1 分别位于 3 的左右子树中。

递归过程：

1. 从根节点 3 开始递归，左右子树分别找到 5 和 1。
2. 5 和 1 分列于根节点 3 的异侧，返回 3 作为结果。