帝国cms下载类网站怎么做,怎么学习建设网站,深圳设计周2021时间,企业邮箱号码从哪里查文章目录1. 题目2. 解题1. 题目
给定一棵二叉树的根节点 root#xff0c;返回给定节点 p 和 q 的最近公共祖先#xff08;LCA#xff09;节点。 如果 p 或 q 之一不存在于该二叉树中#xff0c;返回 null。 树中的每个节点值都是互不相同的。
根据维基百科中对最近公共祖…
文章目录1. 题目2. 解题1. 题目
给定一棵二叉树的根节点 root返回给定节点 p 和 q 的最近公共祖先LCA节点。 如果 p 或 q 之一不存在于该二叉树中返回 null。 树中的每个节点值都是互不相同的。
根据维基百科中对最近公共祖先节点的定义“两个节点 p 和 q 在二叉树 T 中的最近公共祖先节点是后代节点中既包括 p 又包括 q 的最深节点我们允许一个节点为自身的一个后代节点”。 一个节点 x 的后代节点是节点 x 到某一叶节点间的路径中的节点 y。
示例 1:
输入 root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1
输出 3
解释 节点 5 和 1 的共同祖先节点是 3。示例 2:
输入 root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4
输出 5
解释 节点 5 和 4 的共同祖先节点是 5。根据共同祖先节点的定义一个节点可以是自身的后代节点。示例 3:
输入 root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 10
输出 null
解释 节点 10 不存在于树中所以返回 null。提示:
树中节点个数的范围是 [1, 104]。
-109 Node.val 109
所有节点的值 Node.val 是互不相同的。
p ! q来源力扣LeetCode 链接https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
跟之前的 236题 LCA 差不多只是增加了判断 p, q 是否都存在于树中
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {bool findp false, findq false;
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {TreeNode* ans lowestCommonAncestor1(root,p,q);if(findp findq) return ans;return NULL;}TreeNode* lowestCommonAncestor1(TreeNode* root, TreeNode* p, TreeNode* q) {if(!root) return root;if(rootp) findp true;else if(rootq) findq true;auto l lowestCommonAncestor1(root-left,p,q);auto r lowestCommonAncestor1(root-right,p,q);if(rootp || rootq || (l r))return root;return l ? l : r;}
};116 ms 60.3 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
