🌕🌗 235. 二叉搜索树的最近公共祖先

难度: 🌕🌗

问题描述

---

解法 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) {
        // 思路：
        // 递归
        return mySol(root, p, q);
    }

    private TreeNode mySol(TreeNode root, TreeNode p, TreeNode q) {
        // 递归终止条件
        if(root == null) {
            return root;
        }
        // root != null
        if(root == p || root == q) {
            return root;
        }
        TreeNode left = mySol(root.left, p, q);
        TreeNode right = mySol(root.right, p, q);
        if(left == null && right == null) {
            return null;
        }
        if(left != null && right != null) {
            // 两个节点分别在左右子树
            return root;
        }
        if(left == null) {
            return right;
        }
        return left;
    }
}

---

输出 1

---

解法 2 - 特殊

/**
 * 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) {
        // 思路：
        // 利用二叉搜索数的特性
        return mySol(root, p, q); 
    }

    private TreeNode mySol(TreeNode root, TreeNode p, TreeNode q) {
        // 递归终止条件
        if(root == null) {
            return root;
        }
        int min = Math.min(p.val, q.val);
        int max = Math.max(p.val, q.val); 
        // 最近公共祖先肯定在 [min, max] 之间
        if(root.val == min || root.val == max) {
            return root;
        }
        if(root.val > min && root.val < max) {
            return root;
        }
        if(root.val < min) {
            // 往右子树中找
            return mySol(root.right, p, q);
        }
        return mySol(root.left, p, q);
    }
}

---

输出 2