235. Lowest Common Ancestor of a Binary Search Tree

# Easy, DFS

node 1 and node 2.

From root to bottom, if node 1 is in left subtree and node 2 is in right subtree, root is their common ancestor. If both of them are in left or right subtree, continue searching the lowest common ancestor.

Key: 等同于找到这两个点的第一个分叉处。

stop condition is a little hard to think.

Java

/**
 * 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) {
        int pval = p.val, qval = q.val;
                
        if(root.val > Math.max(pval, qval)) 
            return lowestCommonAncestor(root.left, p, q);
        
        if(root.val < Math.min(pval, qval))
            return lowestCommonAncestor(root.right, p, q);
        
        return root;
    }
}

Second Tab