外贸汽车网站有哪些,云南久久建设投资有限公司,代理下单网站开发,南京广告公司招聘题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个结点 p、q#xff0c;最近公共祖先表示为一个结点 x#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大#xff08;一个节点也可以…题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
例如给定如下二叉树: root [3,5,1,6,2,0,8,null,null,7,4] 示例 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。因为根据定义最近公共祖先节点可以为节点本身。
说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。
题目分析
做了一些二叉树的题发现二叉树的查找问题一般都是从左右子树递归去解决也往往都能得到答案因此这道题可以考虑是否能从左右子树进行递归去解决呢 首先要想通过递归来实现就需要先确定临界条件那么临界条件是什么呢换句话说临界条件就是递归中能够直接返回的特殊情况第一点则是最常见的“判空”判断根结点是否是空节点如果是那么肯定就可以马上返回了这是一个临界条件再来考虑题意在以root为根结点的树中找到p结点和q结点的最近公共祖先那么特殊情况是什么呢很显然特殊情况就是根结点就等于q结点或p结点的情况想一下如果根结点为二者之一那么根结点就必定是最近公共祖先了这时直接返回root即可。由此看来这道题就一共有三种特殊情况root q 、root p和rootnull这三种情况均直接返回root即可。 根据临界条件实际上可以发现这道题已经被简化为查找以root为根结点的树上是否有p结点或者q结点如果有就返回p结点或q结点否则返回null。 这样一来其实就很简单了从左右子树分别进行递归即查找左右子树上是否有p结点或者q结点就一共有4种情况 第一种情况左子树和右子树均找没有p结点或者q结点这里特别需要注意虽然题目上说了p结点和q结点必定都存在但是递归的时候必须把所有情况都考虑进去因为题目给的条件是针对于整棵树而递归会到局部不一定都满足整体条件 第二种情况左子树上能找到但是右子树上找不到此时就应当直接返回左子树的查找结果 第三种情况右子树上能找到但是左子树上找不到此时就应当直接返回右子树的查找结果 第四种情况左右子树上均能找到说明此时的p结点和q结点分居root结点两侧此时就应当直接返回root结点了。 综上也不难写出结果了
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(rootp||rootq||!root)return root;TreeNode* leftlowestCommonAncestor(root-left, p, q);TreeNode* rightlowestCommonAncestor(root-right, p, q);if(!left!right)return NULL;else if(left!right)return left;else if(right!left)return right;return root;}
