平衡的定义如下,已知对于树中的任意一个结点,若其两颗子树的高度差不超过1,则我们称该树平衡。现给定指向树根结点的指针TreeNode* root,请编写函数返回一个bool,表示该二叉树是否平衡。
题目分析:
<方法1>:
平衡二叉树是通过左右子树的高度来判断是否为平衡二叉树的,所以我们首先想到的是如何求一个树的高度,求一个树的高度很简单,递归求解,每次求出左右子树的最大高度再加1便是父节点的高度,这样递归下去,便可以求出任何一颗树的高度。
既然可以求出任何一个节点的高度,那么通过再次遍历二叉树,判断任何一个节点的左右子树高度相差是否满足平衡二叉树便可实现平衡二叉树的判断。
求一颗平衡树高度的时间复杂度为O(logN),那么在第二次遍历的时候需要求每个节点的高度时间复杂度为O(NlogN)。其实这个过程大部分都是重复判断的,下面的方法是该方法的浓缩。
<方法2>:
在一次遍历的过程中,既求一个节点的高度,同时该节点是否满足平衡条件,递归函数中一个引用参数返回子节点的高度,然后父节点的高度便可以通过两个子节点的高度求出来,首先判断两个子节点的高度是否满足平衡二叉树,不满足直接返回,满足的情况下,求出当前节点的高度,继续向上递归。
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; } };
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; } } }
//直接遍历求子树深度的方***有效率上的问题,因为遍历过程当中 //子节点会多次求深度,这样没有必要 //思路:后序遍历的方式,保存当前求得的深度, //上层的节点就是当前深度加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); } };
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
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); } };
return False
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; } }
/* * 判断树是否是平衡的有两个条件: * 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; } }
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; } };
// 看了一下大家的解题思路,普遍还是用了寻找深度的方法 // 贡献一种没有寻找深度,纯递归解决的方法 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); } } };
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; } };
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)
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; } };
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); } }
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;
}
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; } };
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; } }
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
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; } }
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
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
}
};