本题要求判断给定的二叉树是否是平衡二叉树
平衡二叉树的性质为: 要么是一棵空树,要么任何一个节点的左右子树高度差的绝对值不超过 1。
一颗树的高度指的是树的根节点到所有节点的距离中的最大值。
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; } }
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; } }
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);//二叉树高度 } }
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; } }
/** * 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); } }
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); } }
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; } }
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; } }
/** * 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)); } }
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; } }
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; } } }
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; }
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; } }
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; }