110. 平衡二叉树

这道题很容易联想到 104. 二叉树的最大深度 的做法。一开始做的时候就知道可以用递归，但是又想到了左右子树的高度相差不大于1，但是子树的子树相差大于1的情况，就开始往这方面多想了。

看了别人的题解才知道，左右子树相差大于1确实可以直接判断为false。

至于子树的子树的情况就要递归调用函数自身了，判断左子树是否为平衡树和判断右子树是否为平衡树再取并，就考虑了子树的子树相差大于1的情况。

这种自顶向下的方法时间复杂度挺大的，效率更高的还得是自底向上的递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root)
    {
        if(root==nullptr) return 0;
        int leftCount = maxDepth(root->left);
        int rightCount = maxDepth(root->right);
        return max(leftCount,rightCount)+1;
    }
    bool isBalanced(TreeNode* root) {
        if(root==nullptr) return true;
        if(abs(maxDepth(root->left)-maxDepth(root->right)) > 1) return false;
        return isBalanced(root->left)&&isBalanced(root->right);
    }
};

自底向上，不太好理解。-1是非平衡的一个标记，若返回的不是-1，则返回树的最大深度。一旦某一个子树不是平衡树，则一直回到上一层返回-1

class Solution {
public:
    int recur(TreeNode* root)
    {
        if(root==nullptr) return 0;
        int _left = recur(root->left);
        if(_left==-1) return -1;
        int _right = recur(root->right);
        if(_right==-1) return -1;
        return abs(_left - _right) < 2 ? max(_left,_right) + 1 : -1;
    }
    bool isBalanced(TreeNode* root)
    {
        return recur(root)!=-1;
    }
};

 

原文地址：http://www.cnblogs.com/uacs2024/p/16851461.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性