请选择 进入手机版 | 继续访问电脑版

Leetcode 235. 二叉搜索树的最近公共祖先

[复制链接]
密战 发表于 2021-1-1 10:32:46 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先体现为一个结点 x,满意 x 是 p、q 的祖先且 x 的深度尽大概大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

 
示例 1:
  1. [b]输入:[/b] root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8[b]输出:[/b] 6 [b]表明: [/b]节点 2 和节点 8 的最近公共祖先是 6。
复制代码
示例 2:
  1. [b]输入:[/b] root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4[b]输出:[/b] 2[b]表明: [/b]节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点自己。
复制代码
 
说明:


  • 所有节点的值都是唯一的。
  • p、q 为差别节点且均存在于给定的二叉搜索树中。
 
充实使用二叉搜索树的特性
  1. /** * 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)     {        if(root==NULL)            return root;        if(root->val>p->val && root->val>q->val)            return lowestCommonAncestor(root->left, p, q);        else if(root->valval && root->valval)            return lowestCommonAncestor(root->right, p, q);        else            return root;    }};
复制代码
这是尾递归,可以转化为非递归形式
  1. /** * 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>p->val && root->val>q->val)                root=root->left;            else if(root->valval && root->valval)                root=root->right;            else                return root;        }                return root;            }};
复制代码
 

来源:https://blog.csdn.net/wwxy1995/article/details/85961793
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )