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

题目描述

思路

本题所给的二叉树是普通的二叉树。做这道题的思路是

1. 如果根节点就为空，那么就返回根节点。
2. （1）如果左子树不为空，并且两个节点都在左子树中（包含左子树的根节点），那么所找的节点就在左子树中，左子树中递归；
   （2）如果右子树不为空，并且两个节点都在又子树中，那么就在右子树中递归；
   （3）如果以上两条都不成立，那么说明一个节点在左子树，一个节点在右子树中，那么就返回该节点。
3. 单独编写一个函数用于判断一个节点是否在一棵树中，该函数返回bool值，方便判断。

解答

/**
 * 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) return root;
        if(root->left && fun(root->left, p) && fun(root->left, q)) return lowestCommonAncestor(root->left, p,q);
        else if(root->right && fun(root->right,p) && fun(root->right, q)) return lowestCommonAncestor(root->right, p,q);
        else return root;
        
    }
    bool fun(TreeNode* root, TreeNode* node)
    {
        if(!root) return false;
        if(root == node) return true;
        else 
            return fun(root->left, node) || fun(root->right, node);
    }
};