LeetCode 1676. 二叉樹的最近公共祖先 IV

Michael阿明 2021-08-15 22:28:33 阅读数:111

本文一共[544]字,预计阅读时长:1分钟~
leetcode 二叉 最近 公共 祖先

文章目錄

1. 題目

給定一棵二叉樹的根節點 root 和 TreeNode 類對象的數組(列錶) nodes,返回 nodes 中所有節點的最近公共祖先(LCA)。
數組(列錶)中所有節點都存在於該二叉樹中,且二叉樹中所有節點的值都是互不相同的。

我們擴展二叉樹的最近公共祖先節點在維基百科上的定義:“對於任意合理的 i 值, n 個節點 p1 、 p2、…、 pn 在二叉樹 T 中的最近公共祖先節點是後代中包含所有節點 pi 的最深節點(我們允許一個節點是其自身的後代)”。

一個節點 x 的後代節點是節點 x 到某一葉節點間的路徑中的節點 y。

示例 1:
在這裏插入圖片描述

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,7]
輸出: 2
解釋: 節點 47 的最近公共祖先是 2

示例 2:
在這裏插入圖片描述

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [1]
輸出: 1
解釋: 單個節點的最近公共祖先是該節點本身。

示例 3:
在這裏插入圖片描述

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [7,6,2,4]
輸出: 5
解釋: 節點 7624 的最近公共祖先節點是 5

示例 4:
在這裏插入圖片描述

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [0,1,2,3,4,5,6,7,8]
輸出: 3
解釋: 樹中所有節點的最近公共祖先是根節點。
提示:
樹中節點個數的範圍是 [1, 10^4]-10^9 <= Node.val <= 10^9
所有的 Node.val 都是互不相同的。
所有的 nodes[i] 都存在於該樹中。
所有的 nodes[i] 都是互不相同的。

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree-iv
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。

2. 解題

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {

public:
TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*> &nodes) {

if(nodes.size()==1) return nodes[0];
TreeNode* ans = lowestCommonAncestor(root, nodes[0], nodes[1]);
for(int i = 2; i < nodes.size(); ++i)
ans = lowestCommonAncestor(root, ans, nodes[i]);
return ans;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{

if(!root || p==root || q==root) return root;
auto l = lowestCommonAncestor(root->left, p, q);
auto r = lowestCommonAncestor(root->right, p, q);
if(l&&r) return root;
return l ? l : r;
}
};
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {

unordered_set<TreeNode*> s;
public:
TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*> &nodes) {

for(auto n : nodes)
s.insert(n);
TreeNode* ans = NULL;
for(auto n : nodes)
ans = lowestCommonAncestor(root, ans, n);
return ans;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{

if(!root || p==root || q==root || s.count(root)) return root;
auto l = lowestCommonAncestor(root->left, p, q);
auto r = lowestCommonAncestor(root->right, p, q);
if(l&&r) return root;
return l ? l : r;
}
};

68 ms 40.8 MB C++


我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號(Michael阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815222753177H.html