Package g1101_1200.s1123_lowest_common_ancestor_of_deepest_leaves

Class Solution

java.lang.Object

g1101_1200.s1123_lowest_common_ancestor_of_deepest_leaves.Solution

public class Solution
extends Object

1123 - Lowest Common Ancestor of Deepest Leaves.<p>Medium</p> <p>Given the <code>root</code> of a binary tree, return <em>the lowest common ancestor of its deepest leaves</em>.</p> <p>Recall that:</p> <ul> <li>The node of a binary tree is a leaf if and only if it has no children</li> <li>The depth of the root of the tree is <code>0</code>. if the depth of a node is <code>d</code>, the depth of each of its children is <code>d + 1</code>.</li> <li>The lowest common ancestor of a set <code>S</code> of nodes, is the node <code>A</code> with the largest depth such that every node in <code>S</code> is in the subtree with root <code>A</code>.</li> </ul> <p><strong>Example 1:</strong></p> <p><img src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/01/sketch1.png" alt="" /></p> <p><strong>Input:</strong> root = [3,5,1,6,2,0,8,null,null,7,4]</p> <p><strong>Output:</strong> [2,7,4]</p> <p><strong>Explanation:</strong> 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.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> root = [1]</p> <p><strong>Output:</strong> [1]</p> <p><strong>Explanation:</strong> The root is the deepest node in the tree, and it&rsquo;s the lca of itself.</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> root = [0,1,3,null,2]</p> <p><strong>Output:</strong> [2]</p> <p><strong>Explanation:</strong> The deepest leaf node in the tree is 2, the lca of one node is itself.</p> <p><strong>Constraints:</strong></p> <ul> <li>The number of nodes in the tree will be in the range <code>[1, 1000]</code>.</li> <li><code>0 <= Node.val <= 1000</code></li> <li>The values of the nodes in the tree are <strong>unique</strong>.</li> </ul> <p><strong>Note:</strong> This question is the same as 865: <a href="https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/" target="_top">https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/</a></p>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	getDep(TreeNode root)
TreeNode	lcaDeepestLeaves(TreeNode root)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

lcaDeepestLeaves

public TreeNode lcaDeepestLeaves(TreeNode root)

getDep

public int getDep(TreeNode root)