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 Sof 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:
這道題讓我們求一棵二叉樹中最深葉結點的最小公共父結點 Lowest Common Ancestor，在 LeetCode 中，有兩道關於 LCA 的題，分別是 Lowest Common Ancestor of a Binary Tree 和 Lowest Common Ancestor of a Binary Search Tree，但是顯然這道題要更加的複雜一些，因為最深的葉結點的個數不確定，可能會有1個，2個，甚至多個，那麼其最小公共父節點的位置也就有多種可能的位置。對於二叉樹的問題，刷題老司機們應該都知道，十有八九都是用遞歸來做，這道題也不例外。在毫無頭緒的時候，就先從最簡單的情況開始分析吧，假如 root 為空，則直接返回 nullptr，假如 root 沒有子結點，其本身就是最深葉結點，返回 root。若 root 有左右子結點，說明左右子樹存在，通常情況下我們會對左右子結點調用遞歸，那麼返回的就是左右子樹分別的最深葉結點的最小公共父節點，但是問題來了，就算分別知道了左右子樹的最深結點的 LCA，怎麼推出當前樹的 LCA？若左子樹的最深葉結點的深度更深，則應該返回左子樹的 LCA，若右子樹的最深葉結點的深度更深，則應該返回右子樹的 LCA，若二者一樣深，則要返回當前結點。這樣的話，對於每個結點 node，必須要分別知道其左右子樹的最深葉結點的深度才行，可以使用一個 getDepth 函數來求任意結點到葉結點的最大深度，葉結點本身的深度為0。有了這個函數，就可以對當前結點的左右子結點計算深度，若深度相同，則返回當前結點，否則對深度大的子結點調用遞歸，怎麼隱約感覺有些二分搜索法的影子在裡面，參見代碼如下：
解法一：
class Solution {
public:
TreeNode* lcaDeepestLeaves(TreeNode* root) {
if (!root) return nullptr;
int left = getDepth(root->left), right = getDepth(root->right);
if (left == right) return root;
return (left > right) ? lcaDeepestLeaves(root->left) : lcaDeepestLeaves(root->right);
}
int getDepth(TreeNode* node) {
if (!node) return 0;
return 1 + max(getDepth(node->left), getDepth(node->right));
}
};
由於計算深度的函數 getDepth 存在大量的重複計算，可以使用一個 HashMap 來保存已經算過深度的結點，這樣再次遇到的時候，直接從 HashMap 中取值即可，可以使計算效率更高一些，參見代碼如下：
解法二：
class Solution {
public:
unordered_map<TreeNode*, int> m;
TreeNode* lcaDeepestLeaves(TreeNode* root) {
if (!root) return nullptr;
int left = getDepth(root->left, m), right = getDepth(root->right, m);
if (left == right) return root;
return (left > right) ? lcaDeepestLeaves(root->left) : lcaDeepestLeaves(root->right);
}
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));
}
};
我們也可以把計算 LCA 和深度放到一個子函數中，讓子函數 helper 既返回以當前結點為根結點的子樹的最深葉結點的 LCA，又返回當前結點的深度。在遞歸函數 helper 中，首先判空，若為空，則返回由 nullptr 和0組成的 pair 對兒。否則分別對左右子結點調用遞歸函數，若左結點的深度大，則返回左子結點和左子結點深度加1組成的 pair 對兒；若右子結點的深度大，則返回右子結點和右子結點深度加1組成的 pair 對兒；剩下的情況就是左右子結點的深度相同，返回當前結點和左子結點深度加1組成的 pair 對兒即可，參見代碼如下：
解法三：
class Solution {
public:
TreeNode* lcaDeepestLeaves(TreeNode* root) {
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};
}
};
再來看一種很類似的寫法，這裡用了兩個全局變量，全局最深葉結點的最小公共父節點 res，以及全局的最大深度 deepest。跟上面的解法思路很類似，也是在遞歸函數 helper 中既算 lCA 又算深度，同時還要更新全局的 res 和 deepest。遞歸函數還需要一個參數 cur，用來保存當前結點的深度，首先用 cur 來更新最大深度 deepest，再判空，若 node 為空，直接返回 cur。再對左右子結點調用遞歸函數，假如此時左右子結點返回的深度都等於最大深度 deepest，說明當前結點 node 就是要求的 LCA，賦值給結果 res，然後返回 left 和 right 中的較大值，就是當前結點 node 的深度，參見代碼如下：
解法四：
class Solution {
public:
TreeNode* lcaDeepestLeaves(TreeNode* root) {
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
LeetCode All in One 題目講解匯總(持續更新中...)