leetcode110. 平衡二叉树

问题描述：

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
/ \
9  20
/  \
15   7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
/ \
2   2
/ \
3   3
/ \
4   4
返回 false 。

思路：深度差小于2，返回true。

上代码，拿去即可运行：

package onlyqi.daydayupgo06.leetcode;public class TreeNode {private Integer value;private TreeNode left;private TreeNode right;public TreeNode() {}public TreeNode(Integer value) {this.value=value;}public TreeNode(Integer value, TreeNode left, TreeNode right) {this.value = value;this.left = left;this.right = right;}public Integer getValue() {return value;}public void setValue(Integer value) {this.value = value;}public TreeNode getLeft() {return left;}public void setLeft(TreeNode left) {this.left = left;}public TreeNode getRight() {return right;}public void setRight(TreeNode right) {this.right = right;}
}

public class Tree {public static void main(String[] args) {TreeNode treeNode1 = new TreeNode(1);TreeNode treeNode2 = new TreeNode(2);TreeNode treeNode3 = new TreeNode(3);TreeNode treeNode4 = new TreeNode(4);TreeNode treeNode5 = new TreeNode(5);TreeNode treeNode6 = new TreeNode(6);TreeNode treeNode7 = new TreeNode(7);treeNode2.setLeft(treeNode4);treeNode2.setRight(treeNode5);treeNode1.setLeft(treeNode2);treeNode1.setRight(treeNode3);treeNode3.setLeft(treeNode6);System.out.println(isBalanced(treeNode1));}public static boolean isBalanced(TreeNode root) {return depth(root) != -1;}private static int depth(TreeNode root) {if (root == null) return 0;int left = depth(root.getLeft());if(left == -1) return -1;int right = depth(root.getRight());if(right == -1) return -1;return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;}
}

运行结果：

我要刷300道算法题，第143道 。 尽快刷到200，每天搞一道  。