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

https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves/

Java

/*
 * @Author: Goog Tech
 * @Date: 2020-09-27 17:55:31
 * @LastEditTime: 2020-09-27 17:55:57
 * @Description: https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves/
 * @FilePath: \leetcode-googtech\#1123. Lowest Common Ancestor of Deepest Leaves\Solution.java
 * @WebSite: https://algorithm.show/
 */

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    // DFS : 深度优先遍历
    // 如果左右子树高度相等,则当前结点为要找的结点
    // 否则要找的结点在高度较大的子树中,进而自底向上的计算高度并返回寻找到的结点
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        if(root == null) return null;
        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);
        return leftDepth == rightDepth ? root : leftDepth > rightDepth ? lcaDeepestLeaves(root.left) : lcaDeepestLeaves(root.right);
    }
    private int depth(TreeNode root) {
        if(root == null) return 0;
        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

Python

'''
Author: Goog Tech
Date: 2020-09-27 17:55:36
LastEditTime: 2020-09-27 17:57:17
Description: https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves/
FilePath: \leetcode-googtech\#1123. Lowest Common Ancestor of Deepest Leaves\Solution.py
WebSite: https://algorithm.show/
'''

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    # DFS : 深度优先遍历
    # 如果左右子树高度相等,则当前结点为要找的结点
    # 否则要找的结点在高度较大的子树中,进而自底向上的计算高度并返回寻找到的结点
    def lcaDeepestLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        def depth(node):
            if not node: return 0
            leftDepth = depth(node.left)
            rightDepth = depth(node.right)
            return max(leftDepth, rightDepth) + 1
        if not root: return None
        leftDepth = depth(root.left)
        rightDepth = depth(root.right)
        return root if leftDepth == rightDepth else self.lcaDeepestLeaves(root.left) if leftDepth > rightDepth else self.lcaDeepestLeaves(root.right)