首页 > 试题广场 >

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

[编程题]判断二叉树是否为平衡二叉树

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

本题要求判断给定的二叉树是否是平衡二叉树

平衡二叉树的性质为: 要么是一棵空树，要么任何一个节点的左右子树高度差的绝对值不超过 1。

一颗树的高度指的是树的根节点到所有节点的距离中的最大值。

示例1

输入

{1,#,2,#,3}

输出

false

示例2

输入

{2,1,3}

输出

true

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

算法知识视频讲解

查看答案及解析

Java

菲尼克斯弗兰克

public class Solution {
    private boolean flag = true;
    public boolean isBalanced (TreeNode root) {
        dfs(root);
        return flag;
    }
    // 返回的是高度不是平衡与否 可以用变量保存！
    public int dfs(TreeNode root) {
        if (root == null) return 0;
        int l = dfs(root.left);
        int r = dfs(root.right);
        if (Math.abs(l - r) > 1) flag = false;
        return l > r ? l+1 : r+1;
    }
}

发表于 2021-09-14 16:55:18 回复(0)

Java

花落梦里

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isBalanced (TreeNode root) {
        // write code here
       if(root==null)
           return true;
        if(root.left==null&&root.right==null)
            return true;
        if(depth(root)==-1)
            return false;
        return true;   
    }
   public int depth(TreeNode root){
       int left,right;
       if(root==null)
           return 0;
       if(root.left==null&&root.right==null)
           return 1;
       left=depth(root.left);
       right=depth(root.right);
       if(Math.abs(left-right)>1)
           return -1;
       if(left==-1||right==-1)
           return -1;
       return Math.max(left,right)+1;
   }
}

发表于 2021-01-03 09:40:33 回复(0)

Java

眼睛想旅行121

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isBalanced (TreeNode root) {

		return getHeight(root) != -1;
	}

	//高度差如果大于1，返回-1
	private int getHeight(TreeNode root) {
		if (root == null)
			return 0;
		int left = getHeight(root.left);
		int right = getHeight(root.right);
		if (left - right > 1 || right - left > 1||right == -1||left == -1)
			return -1;
		return 1 + Math.max(left, right);//二叉树高度
    }
}

发表于 2020-09-17 19:18:09 回复(0)

Java

▓飞蛾扑火ゝ

在求二叉树的高度中，flag记录左右子树高度差，如果有超过1 的就不是，反之则是；

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    static int flag = 0;
    public boolean isBalanced (TreeNode root) {
        // write code here
        if(root==null)
            return true;
        dfs(root);
        return flag<=1;
    }
    public static int dfs(TreeNode root){
        if(root==null)
            return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        flag = Math.max(Math.abs(left-right),flag);
        return Math.max(left,right)+1;
    }
}

发表于 2020-08-14 17:13:56 回复(0)

Java

悟Kong

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean flag=true;
    public boolean isBalanced(TreeNode root) {
        if(root==null)
            return true;
        depth(root);
        return flag;
    }
    public int depth(TreeNode root){
        if(root==null)
            return 0;
        int left=depth(root.left);
        int right=depth(root.right);
        if(Math.abs(left-right)>1)
            flag=false;
        return Math.max(left+1,right+1);
    }
}

发表于 2020-03-06 12:22:20 回复(0)

Java

bLaCk.20181126234896

遍历每个节点自下而上的高度，设置全局变量isBalance，如果一个节点左右高度差大于1则设置isBalance为false。

public class Solution {
    public boolean isBalance = true;
    public boolean isBalanced(TreeNode root) {
        if(root==null)
            return true;
        int h = preorder(root);
        return isBalance;
    }
    public int preorder(TreeNode root){
        if(root==null)
            return 0;
        int left = preorder(root.left)+1;
        int right = preorder(root.right)+1;
        if(Math.abs(left-right)>1)
            isBalance = false;
        return Math.max(left,right);
        
    }
}

发表于 2020-02-16 22:54:31 回复(0)

Java

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)

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)

Java

jRomann

public class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
int l =height(root.left);
int r =height(root.right);
if(Math.abs(l-r)<=1) return isBalanced(root.left)&&isBalanced(root.right);
else
return false;
}
public int height(TreeNode root){
if(root==null) return 0;
else
return Math.max(height(root.left),height(root.right))+1;
}
}

发表于 2018-06-10 16:28:20 回复(0)

Java

小白VI

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int dfs(TreeNode root){
        if(root == null)
            return 0;
        return Integer.max(dfs(root.left),dfs(root.right))+1;
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null)
            return true;
        if(Math.abs(dfs(root.left)-dfs(root.right))>1)
            return false;
        return(isBalanced(root.left) && isBalanced(root.right));
    }
}

发表于 2018-02-24 14:25:17 回复(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)

Java

pp11

public class Solution {
    boolean isBalanced = true;
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;
        getTreeDepth(root);
        return isBalanced;
    }
    public int getTreeDepth(TreeNode root) {
        if (root == null)
            return 0;
        if (root.left == null && root.right == null)
            return 1;
        int leftSubDepth = getTreeDepth(root.left);
        int rightSubDepth = getTreeDepth(root.right);
        if (Math.abs(leftSubDepth - rightSubDepth) > 1)
            isBalanced = false;
        return Math.max(leftSubDepth, rightSubDepth) + 1;
    }
}

发表于 2017-08-06 21:24:05 回复(0)

Java

Holiday_12138

public class Solution {
    public boolean isBalanced(TreeNode root) {
        int[] height = new int[1];
        return judge(root, height);
    }
    
    public boolean judge(TreeNode root, int[] height) {
        if(root == null) {
            height[0] = 0;
            return true;
        }
        else {
            int[] lheight = new int[1];
            int[] rheight = new int[1];
            if(judge(root.left, lheight) && judge(root.right, rheight)) {
                if(Math.abs(lheight[0] - rheight[0]) <= 1) {
                    height[0] = Math.max(lheight[0], rheight[0]) + 1;
                    return true;
                }
            }
        	return false;
        }
    }
}

发表于 2017-06-26 14:06:47 回复(0)

Java

二面挂王

boolean flag = false; public  boolean isBalanced(TreeNode root) { if (root == null) return true;
    judgeBinary(root); if (flag) return false; return true;
} public  int judgeBinary(TreeNode root) { if (root == null) { return 0;
    } int l = judgeBinary(root.left); int r = judgeBinary(root.right); if (l - r > 1 || l - r < -1) { flag = true;
    } return l > r ? l + 1 : r + 1;
}

发表于 2017-06-04 17:49:03 回复(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)

Java

城市里的养猫者

public boolean isBalanced(TreeNode root) { if(root==null){ return true;
    } return height(root)!=-1;
    
} public int height(TreeNode node){ if(node==null){ return 0;
    } int lH=height(node.left); if(lH==-1){ return -1;
    } int rH=height(node.right); if(rH==-1){ return -1;
    } if(lH-rH<-1 || lH-rH>1){ return -1;
    } return Math.max(lH,rH)+1;
}