leetcode-236

leetcode 236

/**
* 2019:10:28不在更新日期
* leetcode-cn-236
* icenaive
*/

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
// p, q 分别在左右子树中时，left和right都会找到值，则当前的节点就是他们的公共祖先
// p, q 在同一颗子树中时，就是 p是q的祖先 或者 q是p的祖先 查找时会返回一个空一个非空，返回非空值就是公共祖先
class Solution {
public:
   TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if(root == nullptr || root == p || root == q) return root;
       TreeNode *left = lowestCommonAncestor(root->left, p, q);
       TreeNode *right = lowestCommonAncestor(root->right, p, q);
       if(left && right) return root;
       return left ? left : right;
       //return left == nullptr ? right : (right == nullptr ? left : root);
   }
};