陈中正的网络日志

LeetCode: Balanced Binary Tree

题目

https://oj.leetcode.com/problems/balanced-binary-tree/

分析

平衡树的判定是每个结点的左右子树的高度差不能超过1

解法一:

判定以某一节点为根的树是否为平衡树可以分解为两步:

  1. 判定左右子树的高度差是否不超过1

  2. 判定左右子树是否为平衡树

解法二:

可以进行一点优化, 让解法以的两个判定在一起完成, 不过两个算法都是一个数量级的。

代码

解法一:

class Solution
{
public:
    bool isBalanced(TreeNode *root)
    {
        if (!root)
            return true;

        int l = depth(root->left);
        int r = depth(root->right);

        if (l-r > -2 && l-r < 2 
                && isBalanced(root->left)
                && isBalanced(root->right))
            return true;
        else
            return false;
    }

    int depth(TreeNode *root)
    {
        if (!root)
            return -1;
        else
            return max(depth(root->left), depth(root->right)) + 1;
    }
};

解法二:

class Solution
{
public:
    bool isBalanced(TreeNode *root)
    {
        if (root == NULL)
            return true;
        else if (depth(root) == -2)
            return false;
        else
            return true;
    }

    int depth(TreeNode *node)
    {
        if (node == NULL)
            return -1;

        int left = depth(node->left);
        if (left == -2)
            return -2;

        int right = depth(node->right);
        if (right == -2)
            return -2;

        if (left-right>1 || left-right<-1)
            return -2;

        return max(left, right) + 1;
    }
};

参考

http://blog.csdn.net/lanxu_yy/article/details/11883083

http://fisherlei.blogspot.com/2013/01/leetcode-balanced-binary-tree-solution.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39028911

Categories:  OJ题解 

« LeetCode: Palindrome Partition LeetCode: Binary Tree Postorder Traversal »