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 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:

  • The given tree will have between 1 and 1000 nodes.
  • Each node of the tree will have a distinct value between 1 and 1000.

这道题让我们求一棵二叉树中最深叶结点的最小公共父结点 Lowest Common Ancestor,在 LeetCode 中,有两道关于 LCA 的题,分别是 Lowest Common Ancestor of a Binary TreeLowest 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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation