luoheng
10/11/2019 - 11:49 AM

lowestCommonAncestor

/**
 * Definition for TreeNode.
 * type TreeNode struct {
 *     Val int
 *     Left *ListNode
 *     Right *ListNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    min, max := 0, 0
    if q.Val > p.Val {
        max, min = q.Val, p.Val
    } else {
        max, min = p.Val, q.Val
    }
    if root.Val > max {
        return lowestCommonAncestor(root.Left, p, q)
    }
    if root.Val < min {
        return lowestCommonAncestor(root.Right, p, q)
    }
    return root
}