Lowest Common Ancestor

LeetCode 236 · View on LeetCode

Find the deepest node that has both p and q as descendants. Recurse left and right. If both sides return non-nil, the current node is the LCA. O(n) time, O(h) space.

package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || root == p || root == q {
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
		return root
	}
	if left != nil {
		return left
	}
	return right
}

func main() {
	//       3
	//      / \
	//     5   1
	//    / \ / \
	//   6  2 0  8
	n6 := &TreeNode{6, nil, nil}
	n2 := &TreeNode{2, nil, nil}
	n0 := &TreeNode{0, nil, nil}
	n8 := &TreeNode{8, nil, nil}
	n5 := &TreeNode{5, n6, n2}
	n1 := &TreeNode{1, n0, n8}
	root := &TreeNode{3, n5, n1}

	fmt.Println(lowestCommonAncestor(root, n5, n1).Val) // 3
	fmt.Println(lowestCommonAncestor(root, n5, n6).Val) // 5
	fmt.Println(lowestCommonAncestor(root, n6, n2).Val) // 5
}