Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1123.html
1123. Lowest Common Ancestor of Deepest Leaves (Medium)
Given the root
of a 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
. if the depth of a node isd
, the depth of each of its children isd + 1
. - The lowest common ancestor of a set
S
of nodes, is the nodeA
with the largest depth such that every node inS
is in the subtree with rootA
.
Note: This question is the same as 865: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4] Output: [2,7,4] Explanation: 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.
Example 2:
Input: root = [1] Output: [1] Explanation: The root is the deepest node in the tree, and it's the lca of itself.
Example 3:
Input: root = [0,1,3,null,2] Output: [2] Explanation: The deepest leaf node in the tree is 2, the lca of one node is itself.
Constraints:
- The number of nodes in the tree will be in the range
[1, 1000]
. 0 <= Node.val <= 1000
- The values of the nodes in the tree are unique.
Related Topics:
Tree, Depth-first Search
Similar Questions:
Solution 1.
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode lcaDeepestLeaves(TreeNode root) { List<TreeNode> deepestLeaves = new ArrayList<TreeNode>(); Map<TreeNode, TreeNode> childParentMap = new HashMap<TreeNode, TreeNode>(); Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { deepestLeaves.clear(); int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); TreeNode left = node.left, right = node.right; if (left == null && right == null) deepestLeaves.add(node); if (left != null) { childParentMap.put(left, node); queue.offer(left); } if (right != null) { childParentMap.put(right, node); queue.offer(right); } } } if (deepestLeaves.size() == 1) return deepestLeaves.get(0); Set<TreeNode> set = new HashSet<TreeNode>(); for (TreeNode node : deepestLeaves) { TreeNode parent = childParentMap.get(node); set.add(parent); } while (set.size() > 1) { List<TreeNode> list = new ArrayList<TreeNode>(set); set.clear(); for (TreeNode node : list) { TreeNode parent = childParentMap.get(node); set.add(parent); } } List<TreeNode> resultList = new ArrayList<TreeNode>(set); return resultList.get(0); } } ############ /** * 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) { return dfs(root).getKey(); } private Pair<TreeNode, Integer> dfs(TreeNode root) { if (root == null) { return new Pair<>(null, 0); } Pair<TreeNode, Integer> l = dfs(root.left); Pair<TreeNode, Integer> r = dfs(root.right); int d1 = l.getValue(), d2 = r.getValue(); if (d1 > d2) { return new Pair<>(l.getKey(), d1 + 1); } if (d1 < d2) { return new Pair<>(r.getKey(), d2 + 1); } return new Pair<>(root, d1 + 1); } }
-
// OJ: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/ // Time: O(N) // Space: O(H) class Solution { int maxDepth = -1, target = 0, cnt = 0; void count(TreeNode *root, int d) { if (!root) return; if (d > maxDepth) { target = 1; maxDepth = d; } else if (d == maxDepth) ++target; count(root->left, d + 1); count(root->right, d + 1); } TreeNode *find(TreeNode *root, int d) { if (!root) return NULL; int before = cnt; auto left = find(root->left, d + 1); if (left) return left; auto right = find(root->right, d + 1); if (right) return right; if (d == maxDepth) ++cnt; return before == 0 && cnt == target ? root : NULL; } public: TreeNode* lcaDeepestLeaves(TreeNode* root) { count(root, 0); return find(root, 0); } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]: def dfs(root): if root is None: return None, 0 l, d1 = dfs(root.left) r, d2 = dfs(root.right) if d1 > d2: return l, d1 + 1 if d1 < d2: return r, d2 + 1 return root, d1 + 1 return dfs(root)[0] ############ # 1123. Lowest Common Ancestor of Deepest Leaves # https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/ # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode: def helper(node): if not node: return 0, None h1, lca1 = helper(node.left) h2, lca2 = helper(node.right) if h1 > h2: return h1 + 1, lca1 if h1 < h2: return h2 + 1, lca2 return h1 + 1, node return helper(root)[1]
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ type pair struct { first *TreeNode second int } func lcaDeepestLeaves(root *TreeNode) *TreeNode { var dfs func(root *TreeNode) pair dfs = func(root *TreeNode) pair { if root == nil { return pair{nil, 0} } l, r := dfs(root.Left), dfs(root.Right) d1, d2 := l.second, r.second if d1 > d2 { return pair{l.first, d1 + 1} } if d1 < d2 { return pair{r.first, d2 + 1} } return pair{root, d1 + 1} } return dfs(root).first }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function lcaDeepestLeaves(root: TreeNode | null): TreeNode | null { const dfs = (root: TreeNode | null): [TreeNode | null, number] => { if (root === null) { return [null, 0]; } const [l, d1] = dfs(root.left); const [r, d2] = dfs(root.right); if (d1 > d2) { return [l, d1 + 1]; } if (d1 < d2) { return [r, d2 + 1]; } return [root, d1 + 1]; }; return dfs(root)[0]; }