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.valare unique. p != qpandqwill 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
}