235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor
 is defined between two nodes v and w as the lowest node in T
 that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. 
Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

用bst的性质遍历就行了:

Just walk down from the whole tree's root as long as both p and q are in the same subtree (meaning their values are both smaller or both larger than root's). This walks straight from the root to the LCA, not looking at the rest of the tree

fb:

需要考虑查找的节点不在树里的情况

fb: 如果祖先是给的那两个结点的一个的话，返回那个结点的parent，否则就返回祖先本身。就这一道题，要求递归非递归两种写法

有一个是根节点, 返回null：简单来说就是你新开一个pointer去track当前node的parent，然后对于当前node的判断是跟leetcode上那道题一样的。

recurision:

如果 p 或 q 是null 怎么办？？？

class Solution {
    TreeNode pre = null;

    public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        // 如果 p 或 q 是null 怎么办？？？
        
        TreeNode left;
        TreeNode right;
        if (p.val < q.val) {
            left = p;
            right = q;
        } else if (p.val > q.val) {
            right = p;
            left = q;
        } else {
            return p;
        }
        TreeNode ans = lowestCommonAncestor(root, left, right);
        if (ans == null) {
            return null;
        }
        if (left.right == right || right.left == left) {
            return pre;
        }
        return ans;
    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root.val > p.val && root.val > q.val) {
            pre = root;

            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            pre = root;

            return lowestCommonAncestor(root.right, p, q);
        } else if (root.val == p.val || root.val == q.val) {
            return pre;
        } else if (root.left.val == p.val && root.right.val == q.val) {
            return root;

        } else {
            return null;
        }
    }

Iterate

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return null;
        }
        TreeNode left;
        TreeNode right;
        if (p.val < q.val) {
            left = p;
            right = q;
        } else if (p.val > q.val) {
            right = p;
            left = q;
        } else {
            return p;
        }

        TreeNode pre = null;
        while (root != null) {

            if (left.val > root.val) {
                root = root.right;
                //continue;
            } else if (right.val < root.val) {
                root = root.left;
                //continue;
            } else if (root.val == right.val || root.val == left.val){
                return pre;
            } else if (root.left.val == left.val && root.right.val == right.val) {
                return root;
            }
            pre = root;
        } // 找不到
         return null;
    }

time： O（h) height

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        /*if (root == null || root == p || root == q) {
            return root;
        }*/
        TreeNode left;
        TreeNode right;
        if (p.val < q.val) {
            left = p;
            right = q;
        } else if (p.val > q.val) {
            right = p;
            left = q;
        } else {
            return p;
        }
        while (root != null) {
            if (left.val > root.val) {
                root = root.right;
                //continue;
            } else if (right.val < root.val) {
                root = root.left;
                //continue;
            } else {
                return root;
            }
        }
        
        return root;
    }
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while ((root.val - p.val) * (root.val - q.val) > 0)
        root = p.val < root.val ? root.left : root.right;
    return root;
}
(in case of overflow, I’d do (root.val - (long)p.val) * (root.val - (long)q.val))

recursion:

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val > p.val && root.val > q.val){
            return lowestCommonAncestor(root.left, p, q);
        }else if(root.val < p.val && root.val < q.val){
            return lowestCommonAncestor(root.right, p, q);
        }else{
            return root;
        }
    }
}

235. Lowest Common Ancestor of a Binary Search Tree

推荐阅读