频道栏目
首页 > 考试 > 其他 > 正文
Leetcode 110 Balanced Binary Tree
2016-10-13 09:08:00         来源:无名山丘,崛起成峰  
收藏   我要投稿

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees ofeverynode never differ by more than 1.

判断树是否是平衡的。

注意平衡树的定义,每一个点的左右子树高度差不超过1,并不是叶子结点的最大深度和最小深度不超过1.

/**
 * 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:
    int dfs(TreeNode* root,bool& res)
    {
        if(!root) return 0;
        int a=dfs(root->left,res)+1;
        int b=dfs(root->right,res)+1;
        if(abs(a-b)>1) res=false;
        return max(a,b);
    }
    bool isBalanced(TreeNode* root) {
        bool res=true;
        dfs(root,res);
        return res;
    }
};


 

点击复制链接 与好友分享!回本站首页
上一篇:Leetcode 109 Convert Sorted List to Binary Search Tree
下一篇:Leetcode 112 Path
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站