菜鸟问一道java题目，check balanced binary tree# JobHunting - 待字闺中
d*n
1 楼
刚开始编leetcode，关于check balanced binary tree，如果纯recursive，时间复杂
度太高，进而想用hashmap 存下各个node的height，减少迭代次数，可是leedcode总说
有Internal Error， 代码如下，应该没问题吧？有没有更搞笑的方法呢？
import java.lang.Math;
import java.util.HashMap;
public class Solution {
HashMap map = new HashMap();
public int getHeight(TreeNode root){
if (root==null){
return 0;
}
else
{
int height;
if (map.containsKey(root)){
height=map.get(root);
}
else{
height=Math.max(getHeight(root.left), getHeight(root.right));
map.put(root,height);
}
return height;
}
}
public boolean isBalanced(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if (root==null) return true;
if (Math.abs(getHeight(root.left)-getHeight(root.right))>1){
return false;
}
else return isBalanced(root.left)&&isBalanced(root.right);
}
}
度太高，进而想用hashmap 存下各个node的height，减少迭代次数，可是leedcode总说
有Internal Error， 代码如下，应该没问题吧？有没有更搞笑的方法呢？
import java.lang.Math;
import java.util.HashMap;
public class Solution {
HashMap
public int getHeight(TreeNode root){
if (root==null){
return 0;
}
else
{
int height;
if (map.containsKey(root)){
height=map.get(root);
}
else{
height=Math.max(getHeight(root.left), getHeight(root.right));
map.put(root,height);
}
return height;
}
}
public boolean isBalanced(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if (root==null) return true;
if (Math.abs(getHeight(root.left)-getHeight(root.right))>1){
return false;
}
else return isBalanced(root.left)&&isBalanced(root.right);
}
}
