二叉树的最近邻祖先节点

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

二叉搜索树的性质, 父节点大于左节点小于右节点, 如果两个节点一个大于父节点的值一个小于, 父节点必为最近邻祖先节点. 要么均在左子树上或均在右子树上, 递归

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root==null)
        return null;
    if(root==p || root==q)
        return root;
    if(root->val > p->val && root->val < q->val || root->val > q->val && root->val < p->val)
        return root;
    else{
        if(root->val > p->val && root->val > q->val){
            return  lowestCommonAncestor(root->left, p, q);
        }
        else{
            return lowestCommonAncestor(root->right, p, q);
        }
    }
}

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

对于一棵普通二叉树, 先左子树走到底, 回退寻找.

 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root==null)
        return null;
    if(root==p || root==q)
        return root;
    TreeNode* left = lowestCommonAncestor(root->left,p,q);
    TreeNode* right = lowestCommonAncestor(root->right,p,q);
    if(left!=null && right!=null)
        return root;
    else{
        if(left!=null)
            return left;
        if(right!=null)
            return right; 
    }
 }