Leetcode Note: Go - Lowest Common Ancestor Of a Binary Search Tree

Lowest Common Ancestor of a Binary Search Tree - LeetCode
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

• Go 言語で取り組んだメモ

所感

Lowest common ancestor - Wikipedia
https://en.wikipedia.org/wiki/Lowest_common_ancestor

• LCA: Lowest common ancestor は共通する最小の祖先のこと
• これを求める関数を実装する

回答

simple recursive and iterative solution - LeetCode Discuss
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/discuss/862386/simple-recursive-and-iterative-solution

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

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if p.Val < root.Val && q.Val < root.Val {
		return lowestCommonAncestor(root.Left, p, q)
	}
	if p.Val > root.Val && q.Val > root.Val {
		return lowestCommonAncestor(root.Right, p, q)
	}
	return root
}

• root, p, q という TreeNode が引数として渡される
  • root: 元となる Binary Search Tree
    • Binary Search Tree なので、自要素の子となる要素の値は大小が分かれる
  • p: 左の要素。値が小さい方
  • q: 右の要素。値が大きい方
• p.Val < root.Val かつ q.Val < root.Val なら
  • lowestCommonAncestor(root.Left, p, q) で再帰
• p.Val > root.Val かつ q.Val > root.Val なら
  • lowestCommonAncestor(root.Right, p, q) で再帰
• それ以外なら root を返す

アプローとしては root.Val が LCA 足り得るのかをチェックして、条件を満たせなかったら子要素を root として再帰していくという感じ