Lintcode 3715 · Lowest Common Ancestor V (最小祖先好题)

这篇具有很好参考价值的文章主要介绍了Lintcode 3715 · Lowest Common Ancestor V (最小祖先好题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

3715 · Lowest Common Ancestor VPRE
Algorithms
Medium

This topic is a pre-release topic. If you encounter any problems, please contact us via “Problem Correction”, and we will upgrade your account to VIP as a thank you.
Description
Given a binary tree with a root node root and an array nodes of objects of class TreeNode, you need to find the Lowest Common Ancestor (LCA, Lowest Common Ancestor) of all nodes in nodes and return it.

Where all the nodes in nodes exist in that binary tree and all the nodes in the binary tree have different values from each other.

Only $39.9 for the “Twitter Comment System Project Practice” within a limited time of 7 days!

WeChat Notes Twitter for more information(WeChat ID jiuzhang15)

The number of nodes in the tree is in the range
[
1
,
1
0
4
]
[1,10
4
]


1
0
9









.




1
0
9
−10
9
≤TreeNode.val≤10
9

All TreeNode.val are unique

All nodes[i] are unique

All nodes[i] exist in the tree

Example
Example 1

Input

root = {3,5,1,6,2,0,8,#,#,7,4}
nodes = [4,7]
Output

2
Explanation

The lowest common ancestor of TreeNode(4) and TreeNode(7) is TreeNode(2)
Example 2

Input

root = {3,5,1,6,2,0,8,#,#,7,4}
nodes = [2]
Output

2
Explanation

The lowest common ancestor of a single node is the node itself
Example 3

Input

root = {3,5,1,6,2,0,8,#,#,7,4}
nodes = [7,2,6,4]
Output

5
Explanation

The lowest common ancestor of TreeNode(7)、TreeNode(2)、TreeNode(6) and TreeNode(4) is TreeNode(5)
Example 4

Input

root = {3,5,1,6,2,0,8,#,#,7,4}
nodes = [0,2,3,1,5,8,6,4,7]
Output

3
Explanation

nodes contains all the nodes in the tree, and the lowest common ancestor of all the nodes in the tree is the root node
Tags
Related Problems

474
Lowest Common Ancestor II
Easy

578
Lowest Common Ancestor III
Medium

3715
Lowest Common Ancestor V
Medium

解法1:套用的labuladong的模板。文章来源地址https://www.toymoban.com/news/detail-734088.html

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: The root node of a binary tree.
     * @param nodes: An array of objects of class TreeNode.
     * @return: The lowest common ancestor of nodes.
     */
    TreeNode* lowestCommonAncestor(TreeNode *root, vector<TreeNode*> &nodes) {
        if (!root) return NULL;
        unordered_set<TreeNode *> nodeSet;
        for (auto pNode : nodes) nodeSet.insert(pNode);
        TreeNode *res = helper(root, nodeSet);
        return res;
    }
private:
    TreeNode* helper(TreeNode *root, unordered_set<TreeNode *> &nodeSet) {
        if (!root) return NULL;
        if (nodeSet.find(root) != nodeSet.end()) return root;
        TreeNode *left = NULL, *right = NULL;
        
        left = helper(root->left, nodeSet);
        right = helper(root->right, nodeSet);
        
        if (left && right) return root;
        return left ? left : right;
    }
};

到了这里,关于Lintcode 3715 · Lowest Common Ancestor V (最小祖先好题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包