首页 > 试题广场 >

判断二叉树是否为平衡二叉树

[编程题]判断二叉树是否为平衡二叉树
  • 热度指数：21339 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
本题要求判断给定的二叉树是否是平衡二叉树
平衡二叉树的性质为: 要么是一棵空树，要么任何一个节点的左右子树高度差的绝对值不超过 1。
一颗树的高度指的是树的根节点到所有节点的距离中的最大值。
示例1

输入

{1,#,2,#,3}

输出

false
示例2

输入

{2,1,3}

输出

true

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C/C++
华科平凡头像 华科平凡

C++ 解法

思路：先写一个函数来求最大深度，对于二叉树的每一个节点，都求它的左子树和右子树的最大深度，如果两个深度之间的差大于1，那么就返回false。不断递归判断即可。

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        if (root == NULL) { return true; }
        if (abs(maxDepth(root->left) - maxDepth(root->right)) > 1) {
            return false;
        }
        return isBalanced(root->left) and isBalanced(root->right);

    }

    int maxDepth(TreeNode *root) {
        if (root == NULL) { return 0; }
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};
发表于 2017-10-27 18:08:47 回复(4)
不负时光头像 不负时光
遍历一次代码即可。。 
class Solution {
public:
    bool isBalanced(TreeNode *root) {
        int depth = 0;
        return isBalanced_helper(root, depth);
    }
    bool isBalanced_helper(TreeNode *root, int &depth) {
        if(root == NULL){
            depth = 0;
            return true;
        }
        int left, right;
        if(isBalanced_helper(root->left, left) && isBalanced_helper(root->right, right)){
            if(abs(left - right) <= 1){
                depth = 1 + max(left, right);
                return true;
            }
        }
        return false;
    }
};

发表于 2016-08-27 09:29:36 回复(3)
HW柯可头像 HW柯可 
/*平衡二叉搜索树（Balanced Binary Tree）具有以下性质：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树*/
import java.util.*;
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null)
            return true;
        if(Math.abs(height(root.left)-height(root.right))>1)
            return false;
        return isBalanced(root.left)&&isBalanced(root.right);
    }
    //利用递归求二叉树的高度
    public int height(TreeNode root){
        if(root == null)
            return 0;
        int left = height(root.left) + 1;
        int right = height(root.right) + 1;
        return left > right ? left : right;
    }

}

编辑于 2020-03-07 22:12:33 回复(6)
LeBronWitness头像 LeBronWitness 
public class Solution {
    public boolean isBalanced(TreeNode root) {
        return dfs(root)>=0;
    }
    
    int dfs(TreeNode root) {
        if(root==null) return 0;
        int left=dfs(root.left),right=dfs(root.right);
        if(left>=0&&right>=0&&Math.abs(left-right)<=1) return 1+Math.max(left,right);
        else return -1;
    }
}
深搜高度，-1判断是否对称
发表于 2019-04-28 20:10:22 回复(0)
Java
詆調壹點头像 詆調壹點 
public class Solution {
    public boolean isBalanced(TreeNode root) {
		if(root == null) return true;
		int left = getHeight(root.left);
		int right = getHeight(root.right);
		if(Math.abs(left - right) > 1) return false;
		return isBalanced(root.left) && isBalanced(root.right);
	}
	public static int getHeight(TreeNode root) {
		if(root == null) return 0;
		int left = getHeight(root.left) + 1;
		int right = getHeight(root.right) + 1;
		return left > right ? left : right;
	}
}

发表于 2017-04-05 18:21:40 回复(3)
猫丫头像 猫丫 
递归算法  public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null)
            return true;
        int left=treeDepth(root.left);
        int right=treeDepth(root.right);
        if(Math.abs(left-right)<=1)
           if (isBalanced(root.left) && isBalanced(root.right) )
            return true;
        return false;
    }
    private int treeDepth(TreeNode root){
        if(root==null)
            return 0;
        if(root.left==null&&root.right==null)
            return 1;
        return Math.max(treeDepth(root.left),treeDepth(root.right))+1;
    }
}
发表于 2016-04-22 23:26:29 回复(1)
LiberHome头像 LiberHome 
class Solution {
    public boolean isBalanced(TreeNode root) {
    //我的第一直觉就是：当BFS到叶子节点的时候记录层数，将所层数运算，绝对值大于1则false，否则true
    //当然，如果发现这样会产生很多重复计算，可能想到自底向上才是最优解,这里先用直觉
        //判空
        if(root == null){
            return true;
        }
        //递归要多熟悉一下
        return Math.abs(hight(root.left)-hight(root.right))<2
        &&isBalanced(root.left)
        &&isBalanced(root.right);
    }

    private int hight(TreeNode node){
        if(node == null){
            return -1;
        }
        return 1+Math.max(hight(node.left),hight(node.right));
    }
}

发表于 2020-07-11 13:30:32 回复(0)
C/C++
Dancer_Wu头像 Dancer_Wu
搜索时加入判断，任意子树不符合要求，停止深搜； 
class Solution {
public:
    int Height(TreeNode *root)    //子树高度
{
	if (root == NULL) return 0;
	return max(Height(root->left), Height(root->right)) + 1;
}
    bool isBalanced(TreeNode *root) {
    if (root == NULL) return true;
	int a = Height(root->left);
	int b = Height(root->right);
	if (abs(a - b) > 1) return false;    
	if (!isBalanced(root->left)) return false;
	return isBalanced(root->right);
    }
};



发表于 2020-04-15 15:22:14 回复(0)
Java
AriesLi头像 AriesLi 
public class Solution {
    public boolean isBalanced(TreeNode root) {
        return balancedHeight(root)==null?false:true;
    }
        // 已经不是平衡二叉树返回null
    Integer balancedHeight(TreeNode node){
        if(node==null) return 0;
        Integer left = balancedHeight(node.left);
        Integer right = balancedHeight(node.right);
        if(left==null||right==null) return null;
        if(Math.max(left, right)-Math.min(left, right) > 1){
            return null;
        }
        return Math.max(left, right)+1;
    }
}

发表于 2020-01-11 18:42:22 回复(0)
|讨厌鬼|头像 |讨厌鬼| 
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (highAndBalanced(root) == -1) return false;
        else return true;
    }

    public int highAndBalanced(TreeNode node){
        if (node == null) return 0;
        int left = highAndBalanced(node.left);
        int right = highAndBalanced(node.right);
        return (left == -1 || right == -1) ? -1 : ((Math.abs(left - right) <= 1) ? (Math.max(left, right) + 1) : -1);
    }
}

发表于 2019-07-29 20:56:34 回复(1)
eddy华头像 eddy华 
//递归求二叉树深度，层次遍历每个结点求深度
import java.util.*;
public class Solution {
    public boolean isBalanced(TreeNode root) {
        Queue<TreeNode> queue= new LinkedList<TreeNode>(); 
        if(root!=null){
            queue.offer(root);
        }
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            if(Math.abs(TreeDepth(node.left)-TreeDepth(node.right))>1){
                return false;
            }
            else{
                  
            if (node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }

            }
        }
        return true;
    }

    public int TreeDepth(TreeNode root) {
        if(root==null)
        return 0; 
        return Math.max(TreeDepth(root.left),TreeDepth(root.right)) + 1;
    }
}

发表于 2019-06-21 10:36:31 回复(0)
tuweilong头像 tuweilong 
//DFS求树的深度。
//先判断当前节点左右子树的深度差小于1.
//如果不符合要求，直接返回false。
//如果符合要求，再分别判断左右子树。
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) 
            return true;
        int depthl = depth(root.left);
        int depth2 = depth(root.right);
        if (Math.abs(depth2 - depthl) <= 1) {
            return isBalanced(root.left) && isBalanced(root.right);
        }  else {
            return false;
        }
    }

    public int depth(TreeNode node) {
        if (node == null) 
            return 0;
        return Math.max(depth(node.left), depth(node.right)) + 1;
    }
}

发表于 2019-06-18 15:28:34 回复(0)
C/C++
yf.dl头像 yf.dl

比较子树高度差来确定平衡，不平衡的子树高度用负数-1表示。

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        return getHeight(root) >= 0;
    }

private:
    int getHeight(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = getHeight(root->left);
        int right = getHeight(root->right);
        if (left >= 0 && right >= 0 && abs(left-right) <= 1)
            return max(left, right) + 1;
        else
            return -1;
    }
};
发表于 2018-08-31 11:18:21 回复(0)
Yrichhhh头像 Yrichhhh 
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(level(root.left) - level(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right))
            return true;
        else
            return false;
    }

    private int level(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(level(root.left), level(root.right));
    }
}
发表于 2018-08-04 11:51:46 回复(0)
Java
。棒★棒㊣餹头像 。棒★棒㊣餹
使用了后序遍历的迭代写法
加入了一个hashmap记录已经访问过的结点的高度方便提供查找
从而实现了从叶节点最后到根的由底层到根的遍历
public class Solution {
    public boolean isBalanced(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode lastNode = null;
        TreeNode nowNode = root;
        Map<TreeNode, Integer> map = new HashMap<>();
        while(nowNode != null || !stack.isEmpty()){
            if(nowNode != null){
                stack.push(nowNode);
                nowNode = nowNode.left;
            }else{
                nowNode = stack.peek();
                if(nowNode.right == null || nowNode.right == lastNode){
                    
                    int lNum = 0;
                    int rNum = 0;
                    if(nowNode.left != null) lNum = map.get(nowNode.left);
                    if(nowNode.right != null) rNum = map.get(nowNode.right);
                    if(Math.abs(lNum - rNum) > 1) return false;
                    map.put(nowNode, Math.max(lNum, rNum) + 1);
                    
                    lastNode = stack.pop();
                    nowNode = null;
                }else{
                    nowNode = nowNode.right;
                }
            }
        }
        
        return true;
    }
}
编辑于 2018-07-15 16:48:28 回复(0)
lucky_me头像 lucky_me

/**

  • Definition for binary tree
  • public class TreeNode {
  • int val;
  • TreeNode left;
  • TreeNode right;
  • TreeNode(int x) { val = x; }

  • }
    */

    public class Solution {
 public boolean isBalanced(TreeNode root) {
     boolean []res = new boolean[1];
     res[0] = true;
     getHeight(root, 1, res);
     return res[0];
 }

 private int getHeight(TreeNode root, int level, boolean[] res) {
     if(root==null)
         return level;
     int lefth = getHeight(root.left, level+1, res);
     if(!res[0])
         return level;
     int righth = getHeight(root.right, level+1, res);
     if(!res[0])
         return level;
     if(Math.abs(lefth-righth)>1)
         res[0] =false;
     return Math.max(lefth,righth);
 }
}
发表于 2018-07-08 22:24:47 回复(0)
C/C++
oceanbase-jonny头像 oceanbase-jonny
递归遍历左右子树的最大深度，超过1则返回false
class Solution {
public:
    bool isBalanced(TreeNode *root) {
        if(!root)
            return true;
        int diff=maxheight(root->left)-maxheight(root->right);
        if(diff>=-1&&diff<=1)
            return isBalanced(root->left)&&isBalanced(root->right);
        else
            return false;
    }
    int maxheight(TreeNode *root){
        if(!root)
            return 0;
        return 1+max(maxheight(root->left),maxheight(root->right));
    }
};
发表于 2018-05-15 10:19:19 回复(0)
透明猫猫头像 透明猫猫
递归的判断子树是否是平衡的，传入一个bool参数，根据这个得到子树的平衡信息，若是平衡的，函数返回值为子树的深度，再与另一个子树的深度进行比较。假如有某个子树存在不平衡的情况，整个树就一定是不平衡的，不用管深度了。 
bool isBalanced(TreeNode *root) {
        if(root==NULL)
            return true;
        if(root->left==NULL&&root->right==NULL)
            return true;
        bool balance=0;
        int lb=subbalance(root->left, &balance);
        if(balance==0)
            return false;
        balance=0;
        int rb=subbalance(root->right, &balance);
        if(balance==0)
            return false;
        if(abs(lb-rb)<=1)
            return true;
        return false;
    }
    
    int subbalance(TreeNode *r, bool *B)
    {
        if(r==NULL)
        {
            *B=1;
            return 0;
        }
        int lb=subbalance(r->left, B);
        if(*B==0)
            return lb;
        int rb=subbalance(r->right, B);
        if(*B==0)
            return rb;
        if(abs(lb-rb)>1)
            *B=0;
        else
            *B=1;
        return lb>rb?(lb+1):(rb+1);
    }

发表于 2017-09-08 22:20:51 回复(0)
Java
阿拉要洗澡头像 阿拉要洗澡
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    public boolean isBalanced(TreeNode root) {
        
        if(root == null){
            return true;
        }
        
        int left=depth(root.left);
        int right=depth(root.right);
        
        if(left-right>1 || left-right<-1){
            return false;
        }else{
            return isBalanced(root.left)&&isBalanced(root.right);
        }
        
    }
    
    public int depth(TreeNode root) {
        
        if(root==null){
            return 0;
        }
        
        
        
        int left=depth(root.left);
        int right=depth(root.right);
        
        if(left>=right){
            return left+1;
        }else{
            return right+1;
        }
        

        
    }
    
    
    
}
发表于 2017-08-18 14:52:03 回复(0)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    bool isBalanced(TreeNode *root) {
        if(fun(root)==-1)
        	return false;
        else
        	return true;
    }
    
    int fun(TreeNode *root)
    {
    	if(root == NULL)
    		return 0;
    		
		int leftHeight = fun(root->left);
		int rightHeight = fun(root->right);
		if(leftHeight==-1 || rightHeight==-1)
			return -1;
		if(abs(leftHeight-rightHeight) > 1)
			return -1;
		return max(leftHeight,rightHeight)+1;
	}
};

发表于 2017-07-28 01:02:07 回复(0)
提交观点

问题信息

树 dfs
难度：
127条回答 20092浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号