235. Lowest Common Ancestor of a Binary Search Tree

Medium

Given a binary search tree (BST), find the lowest common ancestor (LCA) node 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).”

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.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output:
 2

Constraints:

• The number of nodes in the tree is in the range [2, 105].

• -109 <= Node.val <= 109

• All Node.val are unique.

• p != q

• p and q will exist in the BST.

解題

這題利用 BST 左邊子樹必定比 root 小、右邊子樹必定比 root 大的特性來解，不需要使用 recursive，是很漂亮的題目。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root.Val == p.Val && root.Val == q.Val { 
        return root
    }

    temp := root

    for temp != nil {
        if temp.Val == p.Val || temp.Val == q.Val { // 如果 temp 等於其中一節點，回傳
            return temp
        }
        
        // 如果 temp 節點比其中一節點大但比另一節點小，代表他是兩個節點所屬子樹的父節點
        if (temp.Val > p.Val && temp.Val < q.Val) || (temp.Val < p.Val && temp.Val > q.Val) {
            return temp
        } else if temp.Val > p.Val && temp.Val > q.Val  { // 比兩個點都大，往左找
            temp = temp.Left
        } else if temp.Val < p.Val && temp.Val < q.Val  { // 比兩個點都小，往右找
            temp = temp.Right
        }
    }

    return temp
}