在二叉树中找到两个节点的最近公共祖先

C++ 解法, 执行用时: 2ms, 内存消耗: 316KB, 提交时间: 2021-08-09

/**
* struct TreeNode {
*    int val;
*    struct TreeNode *left;
*    struct TreeNode *right;
* };
*/
class Solution {
public:
 /**
  * 
  * @param root TreeNode类 
  * @param o1 int整型 
  * @param o2 int整型 
  * @return int整型
  */
 TreeNode *ret;
 bool dfs(TreeNode *root,int o1,int o2)
 {
     if(!root)
         return false;
     bool l=dfs(root->left,o1,o2);
     bool r=dfs(root->right,o1,o2);
     if((l&&r)||((root->val==o1||root->val==o2)&&(l||r)))
//判断root是否包含o1和o2或root值为o1或o2且o2或o1出现在root子树中
     {
         ret=root;
     }
     return l||r||root->val==o1||root->val==o2;
 }
 int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
     dfs(root,o1,o2);
         return ret->val;
 }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 324KB, 提交时间: 2021-01-02

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        dfs(root, o1, o2);
        return ans->val;
    }
    
    bool dfs(TreeNode* root, const int& p, const int& q) {
        if (nullptr == root)
            return false;
        bool ls = dfs(root->left, p, q);
        bool rs = dfs(root->right, p, q);
        if ((ls && rs) || ((root->val == p || root->val == q) && (ls || rs)))
            ans = root;
        return ls || rs || (root->val == p || root->val == q);
    }
    
    TreeNode* ans;
};

C++ 解法, 执行用时: 2ms, 内存消耗: 328KB, 提交时间: 2022-02-09

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */

    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here

        return dfs(root,o1,o2)->val;
    }
    TreeNode* dfs(TreeNode* root, int o1,int o2){
        if(!root||root->val==o1||root->val==o2)return root;

        TreeNode* left = dfs(root->left,o1,o2);
        TreeNode* right = dfs(root->right,o1,o2);
        
        if(!left) return right;
        if(!right) return left;
        return root;
    }

};

C++ 解法, 执行用时: 2ms, 内存消耗: 332KB, 提交时间: 2021-09-12

// struct TreeNode{
//     int val;
//     TreeNode*left;
//     TreeNode*right;
//     TreeNode(int x):val(x),left(nullptr),right(nullptr){}
// };
//
//最近公共祖先
//分治递归查找
class Solution {
public:
    TreeNode*_lowestCommonAncestor(TreeNode* root, int p, int q){
        //处理段错误
        if(root==nullptr){
            return nullptr;
        }
        //递归终止条件
        if(root->val==p||root->val==q){
            return root;
        }
        TreeNode*left=_lowestCommonAncestor(root->left,p,q);
        TreeNode*right=_lowestCommonAncestor(root->right,p,q);
        //左右子树都没有pq
        if(left==nullptr&&right==nullptr){
            return nullptr;
        }
        //pq都在右子树或者pq都在左子树
        if(left==nullptr||right==nullptr){
            return left==nullptr?right:left;
        }
        return root;
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q){
        return _lowestCommonAncestor(root,p,q)->val;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 332KB, 提交时间: 2021-03-28

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    vector<int> findNode(TreeNode* root, int o1,int o2, vector<int> v){
        if(root==nullptr) return vector<int> {};
        v.push_back(root->val);
        if(root->val==o1) return v;
        else if(root->val==o2) return v;
        vector<int> left=findNode(root->left, o1, o2, v);
        vector<int> right=findNode(root->right, o1, o2, v);
        if(!left.empty()&&!right.empty()) return vector<int> {root->val};
        else if(left.empty()) return right;
        else return left;
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        if(!root) return 0;
        vector<int> v;
        v = findNode(root, o1, o2, v);
        return v.back();
        
    }
};

详情