阅读 9

Lowest Common Ancestor of Deepest Leaves——LeetCode

算法描述

思想

1、当根节点为空时,则直接返回空

2、若只有根节点,则返回根节点

3、若根节点有左右子树,则利用调用本函数,返回左右节点的最深叶结点的最小公共父节点。

定义一个函数,用来返回当前节点的深度,如果左子树和右子树深度一样,则返回根节点,如果左子树深度比右子树深度深,则返回左子树中的最深叶节点的最小公共父节点;如果是右子树比较深,则返回右子树中最深叶节点的最小公共父节点。

代码实现

class Solution {
    int max_deep = 0;
    TreeNode res;
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        if(root == null) return null;
        int left = helper(root.left);
        int right = helper(root.right);
        if(left ==  right){
            return root;
        }
        return left > right ? lcaDeepestLeaves(root.left) : lcaDeepestLeaves(root.right);
        
    }
    
    public int helper(TreeNode root){
        if(root == null){
            return 0;
        }
        return 1 + Math.max(helper(root.left),helper(root.right));
        
    }
    
}
复制代码
关注下面的标签,发现更多相似文章
评论