leetcode-236：二叉樹的最近公共祖先

題目描述

給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”

解題思路

• 分治法
• 如果p或q是root，直接傳回root
• 分别去左右子樹尋找
• 根據左右子樹傳回結果判斷

• 1.左右子樹傳回結果都不為空：說明p和q分别在左右子樹，傳回根結點
    2. 其中一個子樹傳回為空，說明p和q都在那個子樹，傳回的結果是第一個發現的祖先
             

代碼實作

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return root
	}

	if 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
	} else if left != nil {
		return left
	} else {
		return right
	}
}