剑指offer 39.平衡二叉树

剑指offer 39.平衡二叉树

题目

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路

继续偷懒，用前一题的代码，求深度，在返回之前比较一下左右子树深度，若差值大于1，结果置为false。

代码

public class TreeNode {

  int val = 0;
  TreeNode left = null;
  TreeNode right = null;

  public TreeNode(int val) {
    this.val = val;

  }

}

boolean ans = true;

public int TreeDepth(TreeNode root) {
  if (root == null) {
    return 0;
  }
  int left = TreeDepth(root.left);
  int right = TreeDepth(root.right);
  if (Math.abs(left - right) > 1) {
    ans = false;
  }
  return Math.max(left, right) + 1;
}

public boolean IsBalanced_Solution(TreeNode root) {
  int i = TreeDepth(root);
  return ans;
}