云南做商城网站多少钱,做试客刷单的网站有哪些,广告设计招聘岗位要求,如何做好网站针对搜索引擎的seo目录题目思考迭代法题目 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个结点 p、q#xff0c;最近公共祖先表示为一个结点 x#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大#xff0…
目录题目思考迭代法题目 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 例如给定如下二叉搜索树: root [6,2,8,0,4,7,9,null,null,3,5] 思考
对于普通二叉树利用回溯从底向上搜索遇到一个结点的左子树有p右子树有q那么当前结点就是最近公共祖先。 对于有序树从上到下遍历的时候cur结点的数值在[p,q]区间则说明该结点就是cur的最近公共祖先了。 确定返回值以及参数 参数当前结点两个目标结点pq 返回值最近公共祖先TreeNode*
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 确定终止条件 遇到空结点就返回
if(cur NULL) return cur;确定单层逻辑 如果cur在区间左边那么说明区间在cur右子树附近遍历右子树。 如果cur在区间右边说明区间在cur左子树附近遍历左子树。 如果cur在区间中则说明cur就是最近公共祖先。 注意如果找到公共祖先要返回这个结点。
//cur在区间右边所以需要在左子树寻找if(cur-val q-val cur-val p-val){TreeNode* left traversal(cur-left,p,q);//说明找到了公共祖先将这个结点返回if(left !NULL) return left;}//cur在区间左边所以需要在右子树寻找if(cur-val q-val cur-val p-val){TreeNode* right traversal(cur-right,p,q);//说明找到了公共祖先将这个结点返回if(right !NULL) return right;}//cur正好在区间中间说明这个cur就是最近公共祖先返回这个结点return cur;AC代码
/*** 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 {
public:TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q){if(cur NULL) return cur;//cur在区间右边所以需要在左子树寻找if(cur-val q-val cur-val p-val){TreeNode* left traversal(cur-left,p,q);//说明找到了公共祖先将这个结点返回if(left !NULL) return left;}//cur在区间左边所以需要在右子树寻找if(cur-val q-val cur-val p-val){TreeNode* right traversal(cur-right,p,q);//说明找到了公共祖先将这个结点返回if(right !NULL) return right;}//cur正好在区间中间说明这个cur就是最近公共祖先返回这个结点return cur;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root,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 {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {while(root){if(root-val q-val root-val p-val) root root-left;else if(root-val q-val root-val p-val) root root-right;else return root;}return root;}
};
