二叉树平衡检查

[编程题]二叉树平衡检查

热度指数：17658 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

平衡的定义如下，已知对于树中的任意一个结点，若其两颗子树的高度差不超过1，则我们称该树平衡。现给定指向树根结点的指针TreeNode* root，请编写函数返回一个bool，表示该二叉树是否平衡。

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

推荐

九城城主

思路：

定义一个函数visit(TreeNode* root)，功能为递归遍历每一个节点，得到他们各自的左右子树高度，如果其中有节点子树高度差超过1，则返回-1；如果节点子树高度差不超过1，则返回较大的子树高度。

isBalance(TreeNode* root)中首先判断根节点root是否是NULL，是则返回true；不是则调用visit函数，如果返回值为-1，则证明其中有节点的子树高度差超过1，因此返回false；如果不为-1，则返回true。

代码如下所示：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Balance {
public:
    int visit(TreeNode* root)
        {
        int ll, rl;  //ll表示root左子树的高度，rl表示右子树的高度
        if(root->left == NULL) //没有左子节点，则左子树高度为0
            ll = 0;
        else
        {
            int x= visit(root->left);
            if(x == -1)
                return -1;
            ll = x + 1; //左子树的高度为左子节点的子树高度加上左子节点本身，即为x + 1
        }
        if(root->right == NULL)
            rl = 0;
        else
            {
            int x = visit(root->right);
            if(x == -1)
                return -1;//右子树的高度为左子节点的子树高度加上右子节点本身，即为x + 1
            rl = x + 1;
        }
        if(abs(rl - ll) > 1)
            return -1;
        else
            return (rl > ll ? rl : ll);
    }
    bool isBalance(TreeNode* root) {
        // write code here
        if(root == NULL)  //如果根节点为NULL，返回true
            return true;
        if(visit(root) == -1) //如果遍历返回值是-1，则其中有节点的子树高度差超过1，返回false
            return false;
            return true;  //其他返回true
    }
};

编辑于 2015-08-18 20:15:03 回复(2)

Python

ASH975

思路：使用 BSF 层级遍历，若发现单节点则记录，若发现单节点超过两层后则返回 Unbalanced

class Balance:
    def isBalance(self, tree):
        if tree is None: raise TypeError
        depth_diff = 0
        unbalanced_flag = False
        search_queue = [tree]
    
        while search_queue != []:
            if unbalanced_flag: depth_diff += 1
            if depth_diff > 2: return False
            next_queue = []
            for current in search_queue:
                if unbalanced_flag or current.left is None or current.right is None: unbalanced_flag = True
                if current.left is not None: next_queue.append(current.left)
                if current.right is not None: next_queue.append(current.right)
            search_queue = next_queue
        return True

编辑于 2019-01-24 11:15:57 回复(0)

Python

华科平凡

python解法

如果二叉树的每个节点的左子树和右子树的深度不大于1，它就是平衡二叉树。先写一个求深度的函数，再对每一个节点判断，看该节点的左子树的深度和右子树的深度的差是否大于1。

class Balance:
    def isBalance(self, root):
        if not root:
            return True
        if abs(self.maxDepth(root.left) - self.maxDepth(root.right)) > 1:
            return False
        return self.isBalance(root.left) and self.isBalance(root.right)

    def maxDepth(self, root):
        if not root: return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

发表于 2017-10-16 11:30:54 回复(0)