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
}
​