236.md

236. 二叉树的最近公共祖先

递归

对于当前节点，

• 如果两个结点都在左子树，返回左子树中的祖先。
• 如果两个结点都在右子树，返回右子树中的祖先。
• 如果两个结点在左右子树，则当前结点是祖先。
• 如果两个结点不在子树中，则不存在祖先。

递归的子问题只能反应子树中可能是p或者q的祖先，具体还要判断另一边子树情况。

时间复杂度：O(n)。

/**
 * 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 || root == p || root == q) {
            return root;
        }
        // 递归
        TreeNode *l = lowestCommonAncestor(root->left, p, q);
        TreeNode *r = lowestCommonAncestor(root->right, p, q);
        // 单层递归逻辑
        if (l && r) {
            return root;
        }
        if (l) {
            return l;
        }
        return r;
    }
};