题解 | #二叉搜索树的最近公共祖先#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
// 懒人编程法：自顶向下，把问题抛给子树
// 二叉搜索树的特性：按照前序遍历从小到大放置元素值，一个节点的左子树所有节点值都小于此节点值，小于右子树所有节点值。
// 比较p，q，根节点的值，如果p、q在根节点的两端，则根节点就是其第一个公共结点，如果在一端，则抛给左子树或者右子树。
// 终止条件：p、q在根节点的两端。本级任务：判断终止条件。返回：子树处理此任务的结果。
// 时空复杂度：O（n）
public class Solution {
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        if ((p < root.val && root.val < q) || (q < root.val && root.val < p) || (p == root.val) || (q == root.val))
            return root.val;
        if (p < root.val && q < root.val)
            return lowestCommonAncestor(root.left, p, q);
        else
            return lowestCommonAncestor(root.right, p, q);
    }
}