网站内容建设规划,深圳创新网站建设,装修平面设计软件,益阳seo快速排名问题描述#xff1a;给定一个二叉搜索树#xff0c;找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为#xff1a;对于有根树T的两个节点p、q#xff0c;最近公共祖先表示为一个节点x#xff0c;满足x是p和q的祖先#xff0c;且x的深度尽可能大。
…问题描述给定一个二叉搜索树找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为对于有根树T的两个节点p、q最近公共祖先表示为一个节点x满足x是p和q的祖先且x的深度尽可能大。
非递归求解只要找到取值在p和q中间的那个节点即可。如果遍历过程中只要节点小于p和q任意一个则在右节点中找如果节点大于p和q中任意一个则在左节点中找。
public TreeNode ancester(TreeNode root,TreeNode p1,TreeNode p2)
{
int minNumberMath.min(p1.val,p2.val);
int maxNumberMath.max(p1.val,p2.val);
TreeNode currentroot;
while(true)
{
if(current.valmaxNumbercurrent.valminNumber)
{
return current;
}
if(current.valmin)
{
currentcurrent.right;
}
if(current.valmax)
{
currentcurrent.left;
}
}
}
递归方式求解
public TreeNode dfs(TreeNode root,TreeNode p,TreeNode q) { if(root.valMath.max(p.val,q.val)root.valMath.min(p.val,q.val)){return root;} if(root.valMath.min(p.val,q.val)){return dfs(root.right,p,q);} if(root.valMath.max(p.val,q.val)){return dfs(root.left,p,q);} }
