235. Lowest Common Ancestor of a Binary Search Tree(二叉搜索树中的最近公共祖先)
题目描述:
二叉搜索树的特点:二叉搜索树,即二叉排序树
若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
它的中序遍历结果是从小到大排序的。
实现1:递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(p.val>root.val&&q.val>root.val){
return lowestCommonAncestor(root.right,p,q);
}else if(p.val<root.val&&q.val<root.val){
return lowestCommonAncestor(root.left,p,q);
}else{
return root;
}
}
}
实现2:迭代
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(root!=null){
if(p.val>root.val&&q.val>root.val){
root=root.right;
}else if(p.val<root.val&&q.val<root.val){
root=root.left;
}else{
return root;
}
}
return null;
}
}