Leetcode之深度优先搜索（DFS）专题-1123. 最深叶节点的最近公共祖先（Lowest Common Ancestor of Deepest Leaves）

深度优先搜索的解题详细介绍，点击

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

回想一下：

叶节点是二叉树中没有子节点的节点
树的根节点的深度为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
如果我们假定 A 是一组节点 S 的最近公共祖先，<font color="#c7254e" face="Menlo, Monaco, Consolas, Courier New, monospace">S</font> 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。

示例 1：

输入：root = [1,2,3]

输出：[1,2,3]

示例 2：

输入：root = [1,2,3,4]

输出：[4]

示例 3：

输入：root = [1,2,3,4,5]

输出：[2,4,5]

提示：

给你的树中将有 1 到 1000 个节点。
树中每个节点的值都在 1 到 1000 之间。

分析：

根据题目，需要先找到最深的叶子节点，然后求最深的叶子节点的最近公共祖先。

那么我们可以遍历这个树，发现左节点的最大高度=右节点的最大高度时，就可以直接返回这个树，如示例1.

如果高度不等，则再进入高度大的那一边继续遍历，找到左高度=右高度为止。

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

class Solution {

    public TreeNode lcaDeepestLeaves(TreeNode root) {

        if(root==null){

            return null;

        }

        int left = depth(root.left);

        int right = depth(root.right);

        if(left==right){

            return root;

        }else if(left>right){

            return lcaDeepestLeaves(root.left);

        }else if(left<right){

            return lcaDeepestLeaves(root.right);

        }

        return null;

    }

    public int depth(TreeNode node){

        if(node==null) return 0;

        return 1 + Math.max(depth(node.left),depth(node.right));

    }

}

巴特西

Leetcode之深度优先搜索（DFS）专题-1123. 最深叶节点的最近公共祖先（Lowest Common Ancestor of Deepest Leaves）

最新文章

热门文章