110.平衡二叉樹

方法一：自頂向下遞歸

對于當前遍歷到的節點，首先計算左右子樹的高度，如果左右子樹的高度差是否不超過 111，再分別遞歸地遍歷左右子節點，并判斷左子樹和右子樹是否平衡。這是一個自頂向下的遞歸的過程。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isBalanced(TreeNode root) {if(root == null){return true;}else{return Math.abs(height(root.left)- height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);}}public int height(TreeNode root){if(root == null){return 0;}else{return Math.max(height(root.left),height(root.right)) + 1;}}
}

方法二：自底向上遞歸

對于當前遍歷到的節點，先遞歸地判斷其左右子樹是否平衡，再判斷以當前節點為根的子樹是否平衡。如果一棵子樹是平衡的，則返回其高度（高度一定是非負整數），否則返回 ?1。如果存在一棵子樹不平衡，則整個二叉樹一定不平衡。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isBalanced(TreeNode root) {return height(root) >= 0;}public int height(TreeNode root){if(root == null){return 0;}int left = height(root.left);int right = height(root.right);if(left == -1 || right == -1 || Math.abs(left - right) > 1){return -1;}else{return Math.max(left,right) + 1;}}
}