leetcode 236. Lowest Common Ancestor of a Binary Tree (medium)

寻找二叉树节点最小公共祖先

递归
最小公共祖先节点满足q,p点在该节点，或在该节点的左（右）树中。

1. 首先以深度遍历树。
2. 然后，最小公共祖先情况有两种：
   2.1 两个子树中有p,q。
   2.2 它也可以是本身是p或q之一的节点，并且其中一个子树符合条件。

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);return !left ? right : !right ? left : root;}
};