leetcode—二叉树的最近公共祖先

解法思路：

1.利用后序遍历逐步根节点遍历

2.遍历时当前节点存在两种情况：

    a.当前节点的左右子树中包含目标节点，则当前节点就是最近的公共祖先节点

    b.当前节点是目标节点之一，且当前节点的子节点中包含了目标节点，那公共祖先节点就是该节点

解法一：递归

/**
 * 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* res=nullptr;

    bool dfs(TreeNode* node, TreeNode* p, TreeNode* q){
        if(!node)
            return false;
        
        bool left = dfs(node->left, p, q);
        bool right = dfs(node->right, p, q);

        //判断条件left&&right就是情况a
        //判断条件(node->val == p->val || node->val == q->val)&&(left || right)就是情况b
        if((left&&right) || ((node->val == p->val || node->val == q->val)&&(left || right))){
            res = node;
            return true;
        }

        return left || right || (node->val==p->val || node->val==q->val);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //核心思想：使用后序遍历的方法从底向上遍历节点，不能用前序和中序
        //1.分为两种情况：
        //  a.当前节点的左右子树中包含目标节点，则当前节点就是最近的公共祖先节点
        //  b.当前节点是目标节点之一，且当前节点的子节点中包含了目标节点，那公共祖先节点就是该节点
        dfs(root, p, q);
        return res;
    }
};