Categorygithub.com/szhou12/leetcode-goleetcode0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree
package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
Overview
Dependencies
1
Dependents
0

# README

235. Lowest Common Ancestor of a Binary Search Tree

Solution idea

LCA

  • LCA 经典题型: 两个input nodes p, q 一定存在于树中

  • 利用 BST 性质: node X is LCA of p, q iff X's value is between p and q's values.

    1. 如果 current node X 比 p, q 都小, 说明 current node X 太小了, 往它的右子树--增大X值的方向看看呢？
    2. 如果 current node X 比 p, q 都大, 说明 current node X 太大了, 往它的左子树--缩小X值的方向看看呢？
    3. 否则, 看来current node X 恰好夹在p, q中间, 说明 current node X正合适, 就它了