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

港控/mmm° 2022-12-22 16:18 129阅读 0赞

# 题目来源 #

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

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

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

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        
            if (root == null){
        
                return null;
            }
            
            int left = getDepth(root.left);
            int right = getDepth(root.right);
            if (left == right){
        
                return root;
            }
            
            if (left > right){
        
                return lcaDeepestLeaves(root.left);
            }else{
        
                return lcaDeepestLeaves(root.right);
            }
        }
        
        
        private int getDepth(TreeNode root){
        
            if (root == null){
        
                return 0;
            }
            
            return 1 + Math.max( getDepth(root.left) , getDepth(root.right));
        }
    }

![在这里插入图片描述][20201120203745276.png_pic_center]

[1123.]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/2bce56c665674a95a56b64654d2a0edc.png
[20201120203745276.png_pic_center]: /images/20221120/b5848402587c4de39e42a5df6e9ac71f.png