235. 二叉搜索树的最近公共祖先.md

235. 二叉搜索树的最近公共祖先

题目传送门

点击这里

解题思路

求公共祖先，这道题的思路是要记录两个点的线路，如果在一左一右的话那直接返回根节点，如果都在左侧，则返回先遍历到的，还有一种情况是都在根节点的左子树，但是在左子树上的，其两点的分布又分左右了，这时候就是先进入到左侧，然后又变成一左一右的情况。

代码

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

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

	if root.Val == q.Val {
		return root
	}

	leftHas := lowestCommonAncestor(root.Left, p, q)
	rightHas := lowestCommonAncestor(root.Right, p, q)

	if leftHas != nil && rightHas != nil {
		return root
	}

	if leftHas != nil && rightHas == nil {
		return lowestCommonAncestor(root.Left, p, q)
	}

	if leftHas == nil && rightHas != nil {
		return lowestCommonAncestor(root.Right, p, q)
	}
	return nil

}

func getPath(root, target *TreeNode) (path []*TreeNode) {
    // 递归，利用BST的性质，左子树的值都小于根节点，右子树的值都大于根节点，且子树也满足该规则
    node := root
    for node != target {
        path = append(path, node)
        if target.Val < node.Val {
            node = node.Left
        } else {
            node = node.Right
        }
    }
    path = append(path, node)
    return
}

func lowestCommonAncestor(root, p, q *TreeNode) (ancestor *TreeNode) {
    pathP := getPath(root, p)
    pathQ := getPath(root, q)
    for i := 0; i < len(pathP) && i < len(pathQ) && pathP[i] == pathQ[i]; i++ {
        ancestor = pathP[i]
    }
    return
}