L236 二叉树的最近公共祖先

树

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

解：用递归思想来做，p,q要不在同侧，要不在异侧。
1）在左右子树分别返回p,q位置，当前节点为最小父节点。
2）同在左侧，左子树返回p,q中较高的一个，或者递归为1
3）同在右侧同理

减少点儿递归的次数t10%,s0%，当p,q在同一侧的时候，且不为p,q其中一个，不用再继续找了

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || p==root || q==root) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        if(left && left!=p && left!=q) return left;
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        if(right && right!=p&& right!=q) return right;
        // p,q in different sides;
        if(left && right) return root;
        // p,q both in left;
        if(left) return left;
        // p,q both in right;
        else return right;
    }

递归，分别看Left，right是否存在,t10%,s0%

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || p==root || q==root) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        // p,q in different sides;
        if(left && right) return root;
        // p,q both in left;
        if(left) return left;
        // p,q both in right;
        else return right;
    }

原答案t10%,s0%

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