首页 > 试题广场 >

二叉树平衡检查

[编程题]二叉树平衡检查
  • 热度指数：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)
张佃鹏头像 张佃鹏

题目分析：

<方法1>：

      平衡二叉树是通过左右子树的高度来判断是否为平衡二叉树的，所以我们首先想到的是如何求一个树的高度，求一个树的高度很简单，递归求解，每次求出左右子树的最大高度再加1便是父节点的高度，这样递归下去，便可以求出任何一颗树的高度。

       既然可以求出任何一个节点的高度，那么通过再次遍历二叉树，判断任何一个节点的左右子树高度相差是否满足平衡二叉树便可实现平衡二叉树的判断。

       求一颗平衡树高度的时间复杂度为O(logN)，那么在第二次遍历的时候需要求每个节点的高度时间复杂度为O(NlogN)。其实这个过程大部分都是重复判断的，下面的方法是该方法的浓缩。

<方法2>：

      在一次遍历的过程中，既求一个节点的高度，同时该节点是否满足平衡条件，递归函数中一个引用参数返回子节点的高度，然后父节点的高度便可以通过两个子节点的高度求出来，首先判断两个子节点的高度是否满足平衡二叉树，不满足直接返回，满足的情况下，求出当前节点的高度，继续向上递归。

      该方法的时间复杂度只有O(logN)
《程序员面试金典》--程序题目详解： 
class Balance {
public:
    bool isBalance(TreeNode* root) {
        // write code here
		int high=0;
		return isBalance1(root,high);
    }
	bool isBalance1(TreeNode* root,int &high)
	{
		if(root==NULL)
		{
			high=0;
			return true;
		}
		int lhigh,rhigh;
		if(!isBalance1(root->left,lhigh)||!isBalance1(root->right,rhigh))
			return false;
		if(lhigh-rhigh>1||lhigh-rhigh<-1)
			return false;
		high=(lhigh>=rhigh?lhigh:rhigh)+1;
		return true;
	}
};

发表于 2015-10-06 11:24:10 回复(5)
crazychen头像 crazychen 
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) {
        if(root==null){
            return true;
        }else{
            int left = getDeep(root.left);
            int right = getDeep(root.right);
            if(Math.abs(left-right)<=1){
                return isBalance(root.left)&&isBalance(root.right);
            }else{
                return false;
            }
        }       
    }
     
    public int getDeep(TreeNode root){
        if(root!=null){
            int left = getDeep(root.left);
            int right = getDeep(root.right);
            return left>right?left+1:right+1;
        }else{
            return 0;
        }
    }
}

发表于 2015-07-12 12:06:10 回复(5)
低调leo头像 低调leo 
//直接遍历求子树深度的方***有效率上的问题，因为遍历过程当中
//子节点会多次求深度，这样没有必要
//思路：后序遍历的方式，保存当前求得的深度，
//上层的节点就是当前深度加1，所以每个节点只求一次,效率上来了

class Balance {
public:
    bool isBalance(TreeNode *root, int *depth) {
        if (root == NULL) {
            *depth = 0;
            return true;
        }
        int ldepth, rdepth;
        if (isBalance(root->left, &ldepth) && isBalance(root->right, &rdepth)) {
            int diff = ldepth - rdepth;
            if (diff <= 1 && diff >= -1) {
                *depth = (ldepth > rdepth ? ldepth : rdepth) + 1;
                return true;
            }
        }
        return false;
    }
    bool isBalance(TreeNode* root) {
        int depth = 0;
        return isBalance(root, &depth);
    }
};

发表于 2015-08-29 10:46:31 回复(2)
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)
忆水寒头像 忆水寒 

class Balance {
public:
    int depth(TreeNode* root)
    {
        if(root==NULL) return 0;
        int left=depth(root->left);
        int right=depth(root->right);
        return (left>right)?(left+1):(right+1);
    }
    bool isBalance(TreeNode* root) {
        // write code here
        if(root==NULL) return true;
        int diff=depth(root->left)-depth(root->right);
        if(diff>1 ||diff<-1) return false;
        return isBalance(root->left)&&isBalance(root->right);
    }
};

发表于 2016-07-28 15:47:38 回复(0)
谭锅锅头像 谭锅锅
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import math
def getDeep(root):
    if root == None:
        return 0
    else:
        left = getDeep(root.left)
        right = getDeep(root.right)
        return right + 1 if right > left else left + 1
class Balance:
    def isBalance(self, root):
        # write code  here
        if root == None:
            return True
        left = getDeep(root.left)
        right = getDeep(root.right)
        if math.fabs(left-right) <= 1:
            return self.isBalance(root.left) and self.isBalance(root.right)
        else: 
            return False

发表于 2016-12-06 21:40:11 回复(0)
牛客`小强头像 牛客`小强 
public class Balance {
    public boolean isBalance(TreeNode root) {
        // write code here
        if(root==null)
            return true;
        if(Math.abs(deepth(root.left)-deepth(root.right))>1)
            return false;
        else
            return isBalance(root.left)&isBalance(root.right);
    }
    public int deepth(TreeNode root){
        if(root==null)
            return 0;
        return Math.max(deepth(root.left),deepth(root.right))+1;
    }
}

发表于 2015-10-07 19:48:25 回复(1)
Ron头像 Ron 
/*
 * 判断树是否是平衡的有两个条件：
 * 1. 自身的左右子树深度差值<=1
 * 2. 自身的左右子树都为平衡树
 * 但如此计算深度时每次都有重复计算，复杂度太高
 * 因而改进：对每一层做检查时不急于先求出该层高度，而是逐层向下递归，因而返回值是逐层向上的，
 * 若底下有不平衡的直接跳出，最后才会轮到根节点层上看是否为平衡，此时根节点的左右子树深度也刚好求出来
 */
public class Balance{
	public boolean isBalance(TreeNode root) {
		// write code here
		int[] depth = {0};
		boolean res = isBalance(root, depth);
		return res;
	}
	public static boolean isBalance(TreeNode root, int[] depth) {//数组仅一个值，为了传引用
		// write code here
		if(root == null){
			depth[0] = 0;
			return true;
		}
		int[] ldep = {depth[0]};
		int[] rdep = {depth[0]};
		if(isBalance(root.left, ldep) && isBalance(root.right, rdep)){
			int[] diff = new int[1];
			int dif = ldep[0]-rdep[0];
			diff[0] = dif;
			if(diff[0] >= -1 && diff[0] <= 1){
				depth[0] = (ldep[0] > rdep[0] ? ldep[0] : rdep[0]) + 1;
				return true;
			}
		}
		return false;
	}
}

编辑于 2015-10-08 16:40:29 回复(0)
漫漫云天自翱翔头像 漫漫云天自翱翔 
class Balance {
public:
   int  f(TreeNode* root) {
	if (!root)return 0;
	int lchi = f(root->left);
	int rchi = f(root->right);
	if (lchi == -1 || rchi == -1)return -1;
	if (abs(lchi - rchi) > 1)return -1;
	else return 1 + max(lchi, rchi);
}

bool isBalance(TreeNode* root) {
	// write code here
	if (f(root) == -1)return false;
	return true;
}
};

发表于 2021-05-06 11:12:24 回复(0)
yangyt7头像 yangyt7 
// 看了一下大家的解题思路，普遍还是用了寻找深度的方法
// 贡献一种没有寻找深度，纯递归解决的方法
class Balance {
public:
    bool isBalance(TreeNode* root) {
        // write code here
        if(root->left == NULL && root->right!=NULL && (root->right->left!=NULL || root->right->right!=NULL)) return false;
        if(root->right== NULL && root->left!=NULL  && (root->left->left!=NULL  || root->left->right!=NULL)) return false;
        if(root->left == NULL && root->right==NULL) return true;
        if(root->left == NULL && root->right!=NULL && root->right->left==NULL  && root->right->right==NULL) return true;
        if(root->right== NULL && root->left!=NULL  && root->left->left==NULL   && root->left->right==NULL) return true;
        if(root->left&&root->right){
        	return isBalance(root->left)&&isBalance(root->right);
		}
    }
};

发表于 2019-10-05 19:20:46 回复(0)
zbbsyx头像 zbbsyx 
class Balance {
public:
    bool balance = true;
    int height(TreeNode* root){
        if(!root || !balance) return 0;
        int l = height(root -> left);
        int r = height(root -> right);
        if(abs(l - r) > 1) balance = false;
        return max(l,r) + 1;
    }
    bool isBalance(TreeNode* root) {
        // write code here
        height(root);
        return balance;
    }
};

发表于 2019-06-10 15:18:55 回复(0)
MiningMan头像 MiningMan 
class Balance:
    def isBalance(self, root):
        # write code here
        if root is None: return True
        leftHeight = self.getHeigth(root.left)
        rightHeight = self.getHeigth(root.right)
        if leftHeight - rightHeight > 1 or rightHeight - leftHeight > 1:
            return False
        return True

    def getHeigth(self, root):
        """获取树的高度"""
        if root is None:
            return 0
        leftHeight = 1 + self.getHeigth(root.left)
        rigthHeight = 1 + self.getHeigth(root.right)
        return max(leftHeight, rigthHeight)

编辑于 2019-04-16 20:51:54 回复(0)
木然猫猫头像 木然猫猫 

class Balance {
public:
    int treeHeight(TreeNode* node) {
        if (!node) { return 0; }
        int h = 0;
        h = max(h, treeHeight(node->left));
        h = max(h, treeHeight(node->right));
        return h + 1;
    }
    
    bool isBalance(TreeNode* root) {
        if (!root) { return true; }
        return abs(treeHeight(root->left) - treeHeight(root->right)) <= 1;
    }
};

发表于 2018-12-24 18:04:33 回复(0)
OutOfBoundsException头像 OutOfBoundsException 
public class Checker {
    TreeNode prev;
    public boolean checkBST(TreeNode root) {
        // write code here
        if (root == null) return true;
        if (!checkBST(root.left) || (prev != null && prev.val >= root.val)) return false;
        prev = root;
        return checkBST(root.right);
    }
}

编辑于 2018-01-26 17:01:31 回复(0)
fffffffffff头像 fffffffffff 

	public static boolean isBalance(TreeNode root) {





	        // write code here





	        int res = isBalanceCore(root);





	        return res != -1;





	    }





	    





	    public static int isBalanceCore(TreeNode root) {





	        // write code here





	        if(root == null)





	            return 1;





	        





	        int leftHeight = isBalanceCore(root.left);





	        int rightHeight = isBalanceCore(root.right);





	        





	        if(leftHeight == -1 || rightHeight == -1)





	            return -1;





	        if(leftHeight - rightHeight > 1 || leftHeight - rightHeight < -1)





	            return -1;





	        





	        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;





	        





	    }

发表于 2018-01-22 15:44:37 回复(0)
小贾~头像 小贾~ 
class Balance {
public:
    bool isBalance(TreeNode* root) {
        if (root == nullptr) return true;
              //二叉树左右子树高度差
        int tmp = abs(highOfTree(root->left)-highOfTree(root->right));
              //判断是否平衡
        return (tmp <= 1) && isBalance(root->left) && isBalance(root->left);
    }
      //求二叉树高度
    int highOfTree(TreeNode* root) {
        if (root == nullptr) return 0;
        return (highOfTree(root->left) > highOfTree(root->right) ? highOfTree(root->left): highOfTree(root->right)) + 1;
    }
};

发表于 2017-10-31 12:49:29 回复(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)
七月流火29头像 七月流火29 
public class Solution {
    public boolean isBalance(TreeNode root) {
    	return Math.abs(hight(root.left)-hight(root.right))<=1;
    }

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

发表于 2017-09-06 20:40:01 回复(1)
InGodWeTrust头像 InGodWeTrust 
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) {
        if(root==null)	return true;
        int lf=getHigh(root.left);
        int lr=getHigh(root.right);
        if(Math.abs(lf-lr)<=1){
            return isBalance(root.left)&&isBalance(root.right);
        }else{
            return false;
        }
    }
    
    public int getHigh(TreeNode r){
        if(r==null)	return 0;
        int left=getHigh(r.left);
        int right=getHigh(r.right);
        return left>right?left+1:right+1;
    }
}
Java程序员面试金典：http://blog.csdn.net/sinat_22797429/article/details/75451782

发表于 2017-07-21 09:11:30 回复(0)
nomico271头像 nomico271 
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) {
        if(root == null){
            return true;
        }
       int left = getDepth(root.left);
       int right = getDepth(root.right);
       int dif = left - right;
       if(dif < -1 || dif > 1){
           return false;
       }
       return  isBalance(root.left) && isBalance(root.right);
    }
    
    //获取任意结点的深度
    public int getDepth(TreeNode node){
        if (node == null){
            return 0;
        }
        
        int left = getDepth(node.left);
        int right = getDepth(node.right);
        return left > right ? left+1 : right+1;
    }
}

发表于 2017-06-22 18:33:07 回复(0)
提交观点

问题信息

链表 树
难度：
121条回答 25772浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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