Day121 | 灵神 | 二叉树 | 二叉搜索树的最近共公共祖先

1123.最深叶节点的最近公共祖先

1123. 最深叶节点的最近公共祖先 - 力扣（LeetCode）

思路：

笔者第一次做不会做，下面是灵神的思路。注意使用的是后序遍历，因为我们需要叶子结点给上层结点反馈信息

一个重要的思想是把叶子节点所连接的两个空节点看做是叶子结点

推荐先把 236. 二叉树的最近公共祖先 做了，对理解本题做法有帮助

本题最深的叶子可能只有一个，此时这个叶子就是答案。如果最深的叶子不止一个，那么答案为所有最深叶子的最近公共祖先。

方法：递归递归，有递有归

img

回顾 236 题的做法：

  • 如果要找的节点只在左子树中，那么最近公共祖先也只在左子树中。
  • 如果要找的节点只在右子树中，那么最近公共祖先也只在右子树中。
  • 如果要找的节点左右子树都有，那么最近公共祖先就是当前节点。

对于本题，要找的节点是最深的叶子。

如果左子树的最大深度比右子树的大，那么（子树中的）最深叶子就只在左子树中，所以（子树中的）最深叶子的最近公共祖先也只在左子树中。

如果左右子树的最大深度一样呢？当前节点一定是最近公共祖先吗？

不一定。比如上图节点 1 的左右子树最深叶子 0,8 的深度都是 2，但该深度并不是全局最大深度，所以节点 1 并不是答案。

根据以上讨论，正确做法如下：

  1. 从根节点开始递归，同时维护全局最大深度 maxDepth。
  2. 在「递」的时候往下传 depth，用来表示当前节点的深度。
  3. 在「归」的时候往上传当前子树最深的空节点的深度。这里为了方便，用空节点代替叶子，因为最深的空节点的上面一定是最深的叶子。
  4. 设左子树最深空节点的深度为 leftMaxDepth，右子树最深空节点的深度为 rightMaxDepth。如果最深的空节点左右子树都有，即 leftMaxDepth=rightMaxDepth=maxDepth，那么更新答案为当前节点。注意这并不代表我们找到了答案，如果后面发现了更深的空节点，答案还会更新。另外注意，这个判断方式在只有一个最深叶子的情况下，也是正确的。

思考，如果对于完全二叉树，这种做法也是对的嘛？

当然了，因为是后序遍历，所以左右子树遍历结束后才会访问当前结点，也就是如果是完全二叉树的话，最后访问根节点的时候就会把res更新为根结点

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    TreeNode *res;
    int Max_depth=0;
    int get_depth(TreeNode *t,int depth)
    {
        if(t==nullptr)
        {
            Max_depth=max(Max_depth,depth);
            return depth;
        }
        int l=get_depth(t->left,depth+1);
        int r=get_depth(t->right,depth+1);
        if(l==r&&l==Max_depth)
            res=t;
        return max(l,r);
    }
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        get_depth(root,0);
        return res;
    }
};