长沙企业建网站,绵阳市三台县城乡建设局网站,网络推广专员职责,西安小程序开发公司有哪些文章目录1. 题目2. 解题1. 题目
给定一棵二叉树的根节点 root 和 TreeNode 类对象的数组#xff08;列表#xff09; nodes#xff0c;返回 nodes 中所有节点的最近公共祖先#xff08;LCA#xff09;。 数组#xff08;列表#xff09;中所有节点都存在于该二叉树中列表 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
解释: 节点 4 和 7 的最近公共祖先是 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
解释: 节点 7、6、2 和 4 的最近公共祖先节点是 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, vectorTreeNode* 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 || proot || qroot) return root;auto l lowestCommonAncestor(root-left, p, q);auto r lowestCommonAncestor(root-right, p, q);if(lr) 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_setTreeNode* s;
public:TreeNode* lowestCommonAncestor(TreeNode* root, vectorTreeNode* 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 || proot || qroot || s.count(root)) return root;auto l lowestCommonAncestor(root-left, p, q);auto r lowestCommonAncestor(root-right, p, q);if(lr) return root;return l ? l : r;}
};68 ms 40.8 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
