Given a binary tree,find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

Given the following binary search tree:  root = [3,5,1,6,2,8,null,7,4]

        _______3______
       /                  ___5__          ___1__
   /      \        /         6      _2       0       8
         /           7   4

Example 1:

Input: root,p = 5,q = 1
Output: 3
Explanation: The LCA of of nodes  and  is 
513.

Example 2:

Input: root,q = 4
Output: 5
Explanation: The LCA of nodes  and  is,since a node can be a descendant of itself
             according to the LCA deFinition.545

求二叉搜索树的最低公共祖先结点

根据二叉搜索树的性质：位于左子树的结点都比父结点小，位于右子树的结点都比父结点大。

两个结点的最低公共祖先：指两个结点都出现在某个结点的子树中，我们可以从根结点出发遍历一棵树，每遍历一个结点判断两个输入是否在其子树中，如果在其子树中，分别遍历它的所有结点并判断两个输入结点是否在其子树中。直到找到第一个结点，它的子树中同时包括两个输入结点但它的子结点却没有。那么该结点就是最低的公共祖先。

递归

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* p,TreeNode* q) {
        if (root == nullptr || p == nullptr || q == nullptr)
            return root;
        if (max(p->val,q->val) < root->val)
            return lowestCommonAncestor(root->left,p,q);
        else if (min(p->val,q->val) > root->val)
            return lowestCommonAncestor(root->right,q);
        else
            return root;
    }
};

迭代

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* q) {
        if (!root || !p || !q)
            return nullptr;
        int left = p->val,right = q->val;
        while (root)
        {
            int target = root->val;
            if (target > left && target > right)
                root = root->left;
            else if (target < left && target < right)
                root = root->right;
            else
                break;
        }
        return root;
    }
};

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Given a binary search tree (BST),find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree:  root = [6,2,8,4,7,9,null,3,5]

Example 1:

Input: root = [6,5],p = 2,q = 8
Output: 6
Explanation: The LCA of nodes  and  is .
286

Example 2:

Input: root = [6,q = 4
Output: 2
Explanation: The LCA of nodes  and  is,since a node can be a descendant of itself according to the LCA deFinition.
242

Note:

• All of the nodes‘ values will be unique.
• p and q are different and both values will exist in the BST.

代码：

/**
 * DeFinition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x),left(NULL),right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* p,TreeNode* q) {
        int v1 = p -> val;
        int v2 = q -> val;
        int r = root -> val;
        if(v1 > r && v2 < r || v1 < r && v2 > r)
            return root;
        if(v1 == r || v2 == r)
            return root;
        if(v1 < r)
            return lowestCommonAncestor(root -> left,p,q);
        else
            return lowestCommonAncestor(root -> right,q);
    }
};

　　感觉好多递归哦

Given a binary search tree (BST),find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the deFinition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree: root = [6,2,8,4,7,9,null,3,5]

_______6______
       /                  ___2__          ___8__
   /      \        /         0      _4       7       9
         /           3   5

Example 1:

Input: root = [6,5],p = 2,q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2,since a node can be a descendant of itself
according to the LCA deFinition.

Note:

• All of the nodes‘ values will be unique.
• p and q are different and both values will exist in the BST.

# DeFinition for a binary tree node.
class TreeNode:
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def lowestCommonAncestor(self,root,p,q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left,q) #这里需要return，因为不需要回溯，找到就可以了
        elif root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right,q)
        else:
            return root