【leetcode】235-Lowest Common Ancestor of a Binary Search Tree

problem

235. Lowest Common Ancestor of a Binary Search Tree

 二叉搜索树的性质

Lets review properties of a BST:
１．Left subtree of a node N contains nodes whose values are lesser than or equal to node N's value.
２．Right subtree of a node N contains nodes whose values are greater than node N's value.
３．Both left and right subtrees are also BSTs.

百科解释

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 
它的左、右子树也分别为二叉排序树。

 solution1:递归方法：

由于二叉搜索树的特点是左<根<右，所以根节点的值一直都是中间值，大于左子树的所有节点值，小于右子树的所有节点值，那么我们可以做如下的判断，如果根节点的值大于p和q之间的较大值，说明p和q都在左子树中，那么此时我们就进入根节点的左子节点继续递归，如果根节点小于p和q之间的较小值，说明p和q都在右子树中，那么此时我们就进入根节点的右子节点继续递归，如果都不是，则说明当前根节点就是最小共同父节点，直接返回即可。

/**
 * 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) {
        if(!root) return NULL;
        if(root->val > max(p->val, q->val)) 
            return lowestCommonAncestor(root->left, p, q);
        else if(root->val < min(p->val, q->val)) 
            return lowestCommonAncestor(root->right, p, q);
        else return root;
        
    }
};

solution2:迭代方法:

非递归的写法，用个while循环来代替递归调用即可，然后不停的更新当前的根节点，也能实现同样的效果。

/**
 * 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) {
        if(!root) return NULL;
        while(root)
        {
            if(root->val > max(p->val, q->val)) root = root->left;
            else if(root->val < min(p->val, q->val)) root = root->right;
            else break;
        }
        return root;
    }
};

参考

1. leetcode_235_Lowest Common Ancestor of a Binary Search Tree;

完