优于网上博客:110. Balanced Binary Tree 深度优先搜索+记忆化搜索(动态规划)


题目的意思是,给你一颗树,判断它是不是平衡二叉树:

解法一:最暴力的解法:就是每次都判断每个节点的左右子树是否平衡,无疑会有重复计算
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        if(abs(height(root->left)-height(root->right))>1) return false;
        return isBalanced(root->left) && isBalanced(root->right); 
    }
    
    int height(TreeNode* node){
        if(!node) return 0;
        return max(height(node->left),height(node->right))+1;
    }
};


解法二:搜索过程中发现某个子树不是平衡的,那就不再计算这个子树,但是如果它就是一颗平衡树的话,那么效率就比较低了
class Solution {
    public:
        int height(TreeNode *root) {
            if(root == NULL)return 0;
            int l = height(root->left);
            if(l<0) return -1;
            int r = height(root->right);
            if(r<0) return -1;
            if(abs(l-r)>1) return -1;
            return max(l, r) + 1;
        }
        bool isBalanced(TreeNode* root) {
            if(root == NULL)return true;
            return height(root) == -1?false:true;
        }
};


解法三:林奔老师在讲动态规划的时候讲过,记忆化搜索(动态规划递归版),我把访问过的节点高度都记录下来,下次不计算直接返回就好了,不仅代码好理解,也算是复习上课内容了,这里要注意的是,指针也是一个整数哦,一般32位机器指针也是32位,64位指针就是64位了,时间复杂度和空间复杂度都是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:
    bool isBalanced(TreeNode* root) {
        if (root == NULL){
            return true;
        }
        
        int l = dfs(root->left);
        int r = dfs(root->right);
        
        if (abs(l - r) > 1){
            return false;
        }
        return isBalanced(root->left) && isBalanced(root->right); 
    }
    
    int dfs(TreeNode *root){
        if (root == NULL){
            return 0;
        }
        
        map<long long int, int>::iterator it = mp.find((long long int)root);
         if (it != mp.end()){
            return mp[(long long int)root];
        }
        
        int l = dfs(root->left);
        int r = dfs(root->right);
        
        mp[(long long int)root->left] = l;
        mp[(long long int)root->right] = r;
        
        return max(l, r) + 1;
    }
    
private:
    map<long long int, int> mp;
    bool ans;
};
已邀请:

July - 抠细节抠体验,不妥协不将就。

赞同来自:


不错不错 多种解法 逐一优化

要回复问题请先登录注册

返回顶部