首页 > 试题广场 >

二叉树平衡检查

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

热度指数：17625 时间限制：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)

Java

牛客844077796号

（1）递归求树的深度

（2）比较左右子树的深度差的绝对值

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class Balance {
    public boolean isBalance(TreeNode root) {
        return Math.abs(depth(root.left)-depth(root.right))<=1;
    }
    public int depth(TreeNode root){
        if(root==null)
            return 0;
        return Math.max(depth(root.left),depth(root.right))+1;
    }
}

发表于 2022-08-22 09:51:35 回复(0)

Java

猫哥💋

最简解法

public class Balance {

public boolean isBalance(TreeNode root) {
// write code here
if (root == null) return true;
return Math.abs(depth(root.left) - depth(root.right)) <= 1;
}

public int depth(TreeNode root) {
if (root == null) return 0;
int left = 0, right = 0;
return (left = depth(root.left)) > (right = depth(root.right)) ? left+1 : right + 1;
}
}

发表于 2020-03-24 09:08:17 回复(0)

Java

HW柯可

/*平衡二叉树定义(AVL)：它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。*/
public class Balance {
    public boolean isBalance(TreeNode root) {
        if(root == null)
            return true;
        if(Math.abs(height(root.left) - height(root.right)) > 1)
            return false;
        return isBalance(root.left) && isBalance(root.right);
    }
//利用递归法求高度
    public int height(TreeNode root){
        if(root == null)
            return 0;
        int left = height(root.left);
        int right = height(root.right);
        if(left > right)
            return left + 1;
        else
            return right + 1;
    }
}

编辑于 2019-12-12 15:47:44 回复(0)

Java

ST201810301121596

public class Balance {
    public boolean isBalance(TreeNode root) {
        // write code here
        if(root == null){
            return true;
        }
        int err = Math.abs(deep(root.left) - deep(root.right));

        if(err > 1){
            return false;
        }
        return isBalance(root.left) && isBalance(root.right);
    }
    //实现一个方法判断树的深度
    private int deep(TreeNode root){
        if(root == null){
            return 0;
        }
        return Math.max(1+deep(root.left),1+deep(root.right));
    }
}

发表于 2019-06-01 12:26:57 回复(0)

Java

李狗什么

递归法我的思路是在遍历数的深度的同时进行判定，如果有一个节点的高度差超过1那么就不是平衡树。

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class Balance {
    boolean isPass = true;
    public boolean isBalance(TreeNode root) {
        getDepthOfTree(root);
        return isPass;
    }
    
    public int getDepthOfTree(TreeNode node){
        if(node==null){
            return 0;
        }
        int left = getDepthOfTree(node.left);
        int right = getDepthOfTree(node.right);
        if(Math.abs(left-right)>1){
            isPass = false;
        }
        return left>right?left+1:right+1;
    }
}

发表于 2017-10-19 11:12:53 回复(0)

Java

BrownLincoln

思路：递归求高度。但是，对于每个递归下去的结点，都判断是否平衡。由于&&运算符的短路特性，如果某个结点不平衡，则getHeight()并不会被调用。

public class Balance {
    public boolean isBalance(TreeNode root) {
        if(root == null) return true;
        return isBalance(root.left) && isBalance(root.right) && 
            Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1;
    }
    private int getHeight(TreeNode node) {
        if(node == null) {
            return 0;
        }
        return Math.max(getHeight(node.left), getHeight(node.right)) + 1;

    }
}

发表于 2017-08-20 22:04:34 回复(0)

Java

Holiday_12138

public class Balance {
    public boolean isBalance(TreeNode root) {
        if(depth(root)<0)
            return false;
        else
            return true;
    }
    public int depth(TreeNode root){
        if(root==null)
            return 0;
        int leftdepth=depth(root.left);
        int rightdepth=depth(root.right);
        if(leftdepth==-1||rightdepth==-1||leftdepth-rightdepth>1||rightdepth-leftdepth>1)
            return -1;
        else
            return Math.max(leftdepth,rightdepth)+1;
    }
}

发表于 2017-04-12 14:46:06 回复(0)

Java

未缘

import java.util.*;

public class Balance {

public boolean isBalance(TreeNode root) {

// 如果左右子树的高度差的绝对值大于 1 就不平衡

if(deep(root.left)-deep(root.right)>1 || deep(root.left)-deep(root.right) <-1 )

return false;

return true;

}

// 递归求树深度

public int deep(TreeNode root){

while(root==null)

return 0;

return deep(root.left)>deep(root.right)?deep(root.left)+1:deep(root.right)+1;

}

发表于 2017-03-27 23:39:24 回复(0)

Java

上海科比

//底层向上递归的同时判断高度差。
public class Balance {
    private boolean isBalanced = true;
    public boolean isBalance(TreeNode root) {
       getDepth(root);
       return isBalanced;
    }
    public int getDepth(TreeNode root){
        if(root == null)
            return 0;
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        if(Math.abs(left - right) > 1)
            isBalanced = false;
        return right > left ? right+1 : left+1;

    }
}

发表于 2017-03-27 14:58:39 回复(1)

Java

dong1234

//用递归方式得到结点左子树和右子树的高度，返回高度的差值，如果该差值大于1返回false
//如果小于1那需要继续遍历下一个结点用递归的方法
//这里需要判断该结点是否为叶子结点（左右子树都是null） 

import java.util.*;
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Balance {
    public boolean isBalance(TreeNode root) {
        // write code here
        if (root.left!=null && root.right!=null){
            int height = treeNodeHeight(root);
            if(height>1){
                return false;
            }else {
                isBalance(root.left);
                isBalance(root.right);
            }
        }else if(root.left ==null&& root.right != null){
            return false;
        }else  (root.left !=null&& root.right == null){
            return false;
        }
        return true;
    }
    int treeNodeHeight(TreeNode b){
        int lchildh, rchildh = 0;
        if(b==null) return 0;
        else {
            lchildh = treeNodeHeight(b.left) ;
            rchildh = treeNodeHeight(b.right);
            return Math.abs(lchildh-rchildh);
        }
    }
}

编辑于 2017-02-17 19:25:13 回复(0)