原文链接: https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves

英文原文

Given the root of a binary tree, return the lowest common ancestor of its deepest leaves.

Recall that:

• The node of a binary tree is a leaf if and only if it has no children
• The depth of the root of the tree is 0. if the depth of a node is d, the depth of each of its children is d + 1.
• The lowest common ancestor of a set S of nodes, is the node A with the largest depth such that every node in S is in the subtree with root A.

 

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest leaf-nodes of the tree.
Note that nodes 6, 0, and 8 are also leaf nodes, but the depth of them is 2, but the depth of nodes 7 and 4 is 3.

Example 2:

Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree, and it's the lca of itself.

Example 3:

Input: root = [0,1,3,null,2]
Output: [2]
Explanation: The deepest leaf node in the tree is 2, the lca of one node is itself.

 

Constraints:

• The number of nodes in the tree will be in the range [1, 1000].
• 0 <= Node.val <= 1000
• The values of the nodes in the tree are unique.

 

Note: This question is the same as 865: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

中文题目

给你一个有根节点的二叉树，找到它最深的叶节点的最近公共祖先。

回想一下：

• 叶节点 是二叉树中没有子节点的节点
• 树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
• 如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。

 

注意：本题与力扣 865 重复：https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/

 

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：
我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 6、0 和 8 也是叶节点，但是它们的深度是 2 ，而节点 7 和 4 的深度是 3 。

示例 2：

输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点，它是它本身的最近公共祖先。

示例 3：

输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的叶节点是 2 ，最近公共祖先是它自己。

 

提示：

• 给你的树中将有 1 到 1000 个节点。
• 树中每个节点的值都在 1 到 1000 之间。
• 每个节点的值都是独一无二的。

通过代码

高赞题解

解题思路

第一种容想到的常规解法

类似于前序遍历，从根节点开始，分别求左右子树的高度left，和right。

• 情况1：left=right 那么两边子树的最深高度相同，返回本节点
• 情况2：left<right 说明最深节点在右子树，直接返回右子树的递归结果
• 情况2：left>right 说明最深节点在左子树，直接返回右子树的递归结果

其中求子树的高度需要定义一个方法，就是104. 二叉树的最大深度，很简单。

代码

class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
       if(root==null) return null;
       int left=dfs(root.left);
       int right=dfs(root.right);
       if(left==right) return root;
       else if(left<right) return lcaDeepestLeaves(root.right);
       return lcaDeepestLeaves(root.left);
    }
    int dfs(TreeNode  node){
      if(node==null) return 0;
      return 1+Math.max(dfs(node.right),dfs(node.left));
    }
}

第二种方法，

第二种方法其实就是求后序遍历，代码结构有点类似于求最大深度，只不过要想办法保存最近的节点，和返回深度

首先定义一个点来保存最近公共祖先，定义一个pre来保存上一次得到的最近公共祖先的深度。
在递归过程中，带一个参数level表示当前遍历到的节点的深度

如果node为空，返回当前深度。
如果不为空，则当前节点的逻辑为：
分别求左子树和右子树的最大深度，left和right

• 1.left=right 如果相同，并且当前深度大于上一次的最大深度，说明当前节点为最新的最近公共祖先，上一次的没有当前这个深，将当前节点保存在结果中，并将深度pre更新。
• 2.left不等于right 则直接返左右子树的最大深度
  

class Solution {
    TreeNode res = null;
    int pre=0;
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        dfs(root,1);
        return res;

    }
    int dfs(TreeNode  node,int depth){
      if(node==null) return depth;
      int left=dfs(node.left,depth+1);
      int right =dfs(node.right,depth+1);
      if(left==right&&left>=pre){
           res=node;
           pre=left;
      } 
      return Math.max(left,right);
    }
}

统计信息

通过次数	提交次数	AC比率
8539	12126	70.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言