# 1123. Lowest Common Ancestor of Deepest Leaves

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.

``````class Solution {
public:
if (!root) return nullptr;
int left = getDepth(root->left), right = getDepth(root->right);
if (left == right) return root;
}
int getDepth(TreeNode* node) {
if (!node) return 0;
return 1 + max(getDepth(node->left), getDepth(node->right));
}
};
``````

``````class Solution {
public:
unordered_map<TreeNode*, int> m;
if (!root) return nullptr;
int left = getDepth(root->left, m), right = getDepth(root->right, m);
if (left == right) return root;
}
int getDepth(TreeNode* node, unordered_map<TreeNode*, int>& m) {
if (!node) return 0;
if (m.count(node)) return m[node];
return m[node] = 1 + max(getDepth(node->left, m), getDepth(node->right, m));
}
};
``````

``````class Solution {
public:
return helper(root).first;
}
pair<TreeNode*, int> helper(TreeNode* node) {
if (!node) return {nullptr, 0};
auto left = helper(node->left), right = helper(node->right);
if (left.second > right.second) return {left.first, left.second + 1};
if (left.second < right.second) return {right.first, right.second + 1};
return {node, left.second + 1};
}
};
``````

``````class Solution {
public:
TreeNode *res;
int deepest = 0;
helper(root, 0, deepest, res);
return res;
}
int helper(TreeNode* node, int cur, int& deepest, TreeNode*& res) {
deepest = max(deepest, cur);
if (!node) return cur;
int left = helper(node->left, cur + 1, deepest, res);
int right = helper(node->right, cur + 1, deepest, res);
if (left == deepest && right == deepest) {
res = node;
}
return max(left, right);
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1123

Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of a Binary Search Tree

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

https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/discuss/334583/Java-O(n)-Short-and-Simple-Recursion

https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/discuss/334577/JavaC%2B%2BPython-Two-Recursive-Solution

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation