LeetCode.235.Lowest Common Ancestor of BST BST的最近公共祖先

题目描述

235 Lowest Common Ancestor of a Binary Search Tree
https://leetcode-cn.com/problems/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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree:  root = [6,2,8,0,4,7,9,null,null,3,5]

BST

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Note:

• All of the nodes’ values will be unique.
• p and q are different and both values will exist in the BST.

---

相似题目

LeetCode.235.Lowest Common Ancestor of BST BST的最近公共祖先
LeetCode.236.Lowest Common Ancestor of a Binary Tree 二叉树的最近公共祖先

---

解题过程

做这道题的时候没注意到是 BST 树，没用到 BST 的性质，写成了通用的二叉树最低公共祖先的判断方法，专门写了个判断 root 中是否包含 p,q 的方法 containNodes，每次递归过程中加了一次遍历，时间复杂度为 O(n^2)，但还是通过了。

其实可以利用 BST 的性质，左子树所有结点值都小于根，右子树所有结点值都大于根，直接把 p,q 的值和 root 比较，然后递归的在左右子树中找最近公共祖先，如果 p,q 一个比 root 小一个比 root 大，则 root 就是 p,q 的最近公共祖先，时间复杂度为O(n)

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

// 非递归先序遍历，判断root中是否包含p和q
public boolean containNodes(TreeNode root, TreeNode p, TreeNode q) {
    if (null == root) {
        return false;
    }
    boolean hasP = false;
    boolean hasQ = false;
    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root);
    TreeNode cur = root;
    while (!stack.isEmpty() || null != cur) {
        while (null != cur) {
            hasP = cur == p || hasP;
            hasQ = cur == q || hasQ;
            cur = cur.left;
            if (null != cur) {
                stack.push(cur);
            }
        }
        cur = stack.pop();
        if (null != cur.right) {
            stack.push(cur.right);
        }
        cur = cur.right;
    }
    return hasP && hasQ;
}

---

GitHub代码

algorithms/leetcode/leetcode/_235_LowestCommonAncestorOfBST.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_235_LowestCommonAncestorOfBST.java

---