首页 > 编程语言(其他) > 【LeetCode】110. Balanced Binary Tree

【LeetCode】110. Balanced Binary Tree

问题描述

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 of every node never differ by more than 1.

判断一棵树是否为平衡树。平衡树的定义为:每个节点的左右子树的高度差不大于1。

问题分析

遍历树,对于每个节点,求出其左右子树的高度,然后判断两者的差是否大于1,大于1,直接返回False;否则,继续遍历左子树和右子树。

代码

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root==0) return true;
        if(root->left==0&&root->right==0) return true;
        TreeNode* p = root;
        int r = depth(p->right,0);
        int l = depth(p->left,0);
        if(abs(r-l)>1) {
            return false;
        }
        return isBalanced(p->left)&&isBalanced(p->right);   
    }

    int depth(TreeNode* p, int level) {
        if(p==0) return level;
        level++;
        int l1 = depth(p->left, level);
        int l2 = depth(p->right, level);
        return l1>l2?l1:l2;
    } 
};
作者:zgljl2012 发表于2017/1/9 10:13:20 原文链接
阅读:133 评论:0 查看评论
分类: 编程语言(其他) 标签: