给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 1.对于该题的最近的公共祖先定义:对于有根树T的两个结点p、q,最近公共祖先LCA(T,p,q)表示一个结点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先. 2.二叉搜索树是若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值 3. 所有节点的值都是唯一的。 4.p、q 为不同节点且均存在于给定的二叉搜索树中。 数据范围: 3<=节点总数<=10000 0<=节点值<=10000 如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5},如下图:-笔试面试资料

这是qklbishe.com第18397 篇笔试面试资料
提供答案分析,通过本文《给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 1.对于该题的最近的公共祖先定义:对于有根树T的两个结点p、q,最近公共祖先LCA(T,p,q)表示一个结点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先. 2.二叉搜索树是若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值 3. 所有节点的值都是唯一的。 4.p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围: 3<=节点总数<=10000 0<=节点值<=10000
如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5},如下图:-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1.对于该题的最近的公共祖先定义:对于有根树T的两个结点p、q,最近公共祖先LCA(T,p,q)表示一个结点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先.
2.二叉搜索树是若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值
3.所有节点的值都是唯一的。
4.p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围:
3<=节点总数<=10000
0<=节点值<=10000

如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5},如下图:
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。      1.对于该题的最近的公共祖先定义:对于有根树T的两个结点p、q,最近公共祖先LCA(T,p,q)表示一个结点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先.      2.二叉搜索树是若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值      3. 所有节点的值都是唯一的。      4.p、q 为不同节点且均存在于给定的二叉搜索树中。           数据范围:      3&lt;=节点总数&lt;=10000      0&lt;=节点值&lt;=10000               如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5},如下图:

C++

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。      1.对于该题的最近的公共祖先定义:对于有根树T的两个结点p、q,最近公共祖先LCA(T,p,q)表示一个结点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先.      2.二叉搜索树是若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值      3. 所有节点的值都是唯一的。      4.p、q 为不同节点且均存在于给定的二叉搜索树中。           数据范围:      3&lt;=节点总数&lt;=10000      0&lt;=节点值&lt;=10000               如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5},如下图: breeze_blows

1.如果当前节点值比p和q都小,证明q与p在当前节点右子树中,应该在右子树中找
2.如果当前节点值比p和q都大,证明q与p在当前节点左子树中,应该在左子树中找
3.如果当前节点值介于p和q之间,证明找到了
ps:在二叉树中找最近公众祖先的方法也可以用在这里,不过没有利用二叉搜索树特有的性质
/**  * struct TreeNode {  *	int val;  *	struct TreeNode *left;  *	struct TreeNode *right;  *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  * };  */ class Solution { public:     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param root TreeNode类       * @param p int整型       * @param q int整型       * @return int整型      */     int lowestCommonAncestor(TreeNode* root, int p, int q) {         // write code here         TreeNode *resNode = root;         while(1){             if(resNode->val < p && resNode->val < q){                 resNode = resNode->right;             } else if(resNode->val > p && resNode->val > q){                 resNode = resNode->left;             } else{                 break;             }         }         return resNode->val;                  //没有考虑二叉搜索树的性质 //         if(root == nullptr) return -1; //         if(root->val == p || root->val == q){ //             return root->val; //         } //         int left = lowestCommonAncestor(root->left, p, q); //         int right = lowestCommonAncestor(root->right, p, q); //         if(left != -1 && right != -1) return root->val; //         if(left != -1) return left; //         if(right != -1) return right; //         return -1;             } };      

今天 10:32:28 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 1.对于该题的最近的公共祖先定义:对于有根树T的两个结点p、q,最近公共祖先LCA(T,p,q)表示一个结点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先. 2.二叉搜索树是若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值 3. 所有节点的值都是唯一的。 4.p、q 为不同节点且均存在于给定的二叉搜索树中。 数据范围: 3<=节点总数<=10000 0<=节点值<=10000 如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5},如下图:-笔试面试资料

提供最优质的资源集合

立即查看 了解详情