My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null)
return true;
return getDepth(root) == -1 ? false : true;
}
private int getDepth(TreeNode root) {
if (root == null)
return 0;
int left = getDepth(root.left);
if (left == -1)
return -1;
int right = getDepth(root.right);
if (right == -1)
return -1;
if (Math.abs(left - right) < 2)
return 1 + Math.max(left, right);
else
return -1;
}
}
My test result:
题目是easy级别，但可能，深夜，我太累了，脑子转不过来，于是就没写出来。
本来不打算写这道题目的，但还想拼一下，就写了。
题目本身也是需要想想的。
具体看这个博客吧。
http://bangbingsyb.blogspot.com/2014/11/leetcode-balanced-binary-tree.html
我想说明的是，什么 depth of tree and height of tree
depth of node n: length of path from n to root.
所以说， depth of subtree 指的应该就是 这棵subtree最大的深度，以该subtree结点为root。
所以， balanced binary tree的左右subtree的最大深度，不能超过1.
然后这个规则继续递归给subtree的左右subtree。
然后需要bottom-up 来进行判断。具体看代码吧。
还有就是，
height of node n: length of path from n to its deepest descendent.
= depth of the subtree.
**
总结： Tree, DFS, Balance binary tree, depth of tree, height of tree
**
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null)
return true;
return helper(root) == -1 ? false : true;
}
/** if return -1, means it is not balanced */
private int helper(TreeNode root) {
if (root == null)
return 0;
int left = helper(root.left);
if (left == -1)
return -1;
int right = helper(root.right);
if (right == -1)
return -1;
if (Math.abs(left -right) <= 1)
return Math.max(left, right) + 1;
else
return -1;
}
}
这道题目是从下往上的dfs
cf聊了那么多家，投了那么多家，竟然一家都没给机会。。
不再畏惧了。没什么准备不准备的。
海投，开始吧！
刚把apple投了。
Anyway， Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int ret = helper(root);
return ret == -1 ? false : true;
}
private int helper(TreeNode root) {
if (root.left == null && root.right == null) {
return 1;
}
else if (root.left == null) {
int right = helper(root.right);
if (right == -1 || right > 1) {
return -1;
}
else {
return 1 + right;
}
}
else if (root.right == null) {
int left = helper(root.left);
if (left == -1 || left > 1) {
return -1;
}
else {
return 1 + left;
}
}
else {
int left = helper(root.left);
int right = helper(root.right);
if (left == -1 || right == -1) {
return -1;
}
else if (Math.abs(left - right) > 1) {
return -1;
}
else {
return 1 + Math.max(left, right);
}
}
}
}
差不多的思路。
Anyway, Good luck, Richardo! -- 08/28/2016
