Given a rooted binary tree, return the lowest common ancestor of its deepest leaves.
Recall that:
The node of a binary tree is a leaf if and only if it has no children
The depth of the root of the tree is 0, and if the depth of a node is d, the depth of each of its children is d+1.
The lowest common ancestor of a set S of nodes is the node A with the largest depth such that every node in S is in the subtree with root A.
Example 1:
Input: root = [1,2,3]
Output: [1,2,3]
Explanation:
The deepest leaves are the nodes with values 2 and 3.
The lowest common ancestor of these leaves is the node with value 1.
The answer returned is a TreeNode object (not an array) with serialization "[1,2,3]".
Example 2:
Input: root = [1,2,3,4]
Output: [4]
Example 3:
Input: root = [1,2,3,4,5]
Output: [2,4,5]
Constraints:
The given tree will have between 1 and 1000 nodes.
Each node of the tree will have a distinct value between 1 and 1000.
Solution:
/**
* 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 {
int maxDepth = -1;
public TreeNode lcaDeepestLeaves(TreeNode root) {
Set<TreeNode> max = new HashSet();
pre(root, max, 0);
return post(root, max);
}
private TreeNode post(TreeNode root, Set<TreeNode> max) {
if (root == null) return root;
if (max.contains(root)) return root;
TreeNode left = post(root.left, max);
TreeNode right = post(root.right, max);
if (left != null && right != null) return root;
else if (left != null) return left;
else return right;
}
private void pre(TreeNode root, Set<TreeNode> max, int depth) {
if (root == null) return;
if (root.left == null && root.right == null) {
if (depth > maxDepth) {
maxDepth = depth;
max.clear();
max.add(root);
} else if (depth == maxDepth) {
max.add(root);
}
}
pre(root.left, max, depth + 1);
pre(root.right, max, depth + 1);
}
}