LeetCode二叉树的最近公共祖先问题
这个题目是给定一个二叉搜索树,找到该树种两个指定节点的最近公共祖先。如下所示:
首先这个题目要从二叉搜索树入手,二叉搜索树有一个特点,就是它或者是一棵空树,或者是具有以下性质的二叉树:若它的左子树不空,则左子树上所有节点均小于它根节点的值;若它的的右子树不空,则右子树上所有节点的值均大于它的根节点的值,并且它的左右子树也分别是二叉搜索树。
在了解了二叉搜索树的定义之后,我们可以考虑用递归的方法,如果p节点的值小于根节点的值,并且q节点的值大于根节点的值,这个时候我们就可以认为根节点就是p和q节点的最近公共祖先。第二种情况就是p和q节点的值都要大于根节点的值,这个时候可以认为我们要找的最近祖先是在当前根节点的右子树中。第三种情况就是p和q的节点的值都小于根节点的值,这个时候我们可以认为要找的最近公共祖先在当前根节点的左子树中。有了上面的推导,我们可以用递归的方法进行解答:
class Solution {
TreeNode res = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
lca(root, p, q);
return res;
}
public void lca(TreeNode root, TreeNode p, TreeNode q){
if((root.val - p.val)*(root.val - q.val) <= 0){
res = root;
}else if((root.val < p.val)&&(root.val < q.val)){
lca(root.right, p, q);
}else{
lca(root.left, p, q);
}
}
}
其实理解了二叉搜索树的定义和递归的思想,这道题目就很容易解答了,希望对大家对二叉搜索树的理解和递归思想的理解有所帮助,谢谢。