d**********n
发帖数: 132 | 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);
}
} |
j********g
发帖数: 80 | 2 可以不用get_height(), height当个参数遍历的时候传下去，从底层往上return, 在每
个node判断返回的height是否合法. |
d**********n
发帖数: 132 | 3 先谢谢jordan，有想过直接从底层往上return，但是如果不保存height，之后每个父结
点判断时，还得迭代进入subtree求height？ |
l*****a
发帖数: 14598 | 4 我的体会是这种题最好定义一个结构
class Info {
int depth;
boolean balanced;
}
来记录当前子树信息，因为这种题都需要用递归从root一直到leaves.
而且求depth要递归，判断balanced还要递归，最好一次递归就把所需要的值都存下来
类似的还有那道求树中两结点间最大path那题
这是我的code,见笑了
public boolean isBalanced(TreeNode root) {
return depth(root).balanced;
}
public Info depth(TreeNode root) {
if(root==null) return new Info(true,0);
Info leftInfo=depth(root.left);
Info rightInfo=depth(root.right);
boolean bo=(Math.abs(leftInfo.depth-rightInfo.depth)<=1)&&(leftInfo.
balanced==true)&&(rightInfo.balanced==true);
int de=Math.max(leftInfo.depth,rightInfo.depth)+1;
return new Info(bo,de);
}
【在 d**********n 的大作中提到】
: 刚开始编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;
|
j********g
发帖数: 80 | 5 楼上的代码解释了你的疑问。大概就是那个意思，可以自定义结构，也可以在每次调用
的时候创建个局部变量。
【在 d**********n 的大作中提到】
: 先谢谢jordan，有想过直接从底层往上return，但是如果不保存height，之后每个父结
: 点判断时，还得迭代进入subtree求height？
|
d**********n
发帖数: 132 | 6 嗯，这样的确方便不少，不过有一个地方还没怎么想清楚，如果重新迭代，subtree的
Info是会再计算一遍，还是已经存储了呢，是不是开个全局的structure会更省力？
【在 l*****a 的大作中提到】
: 我的体会是这种题最好定义一个结构
: class Info {
: int depth;
: boolean balanced;
: }
: 来记录当前子树信息，因为这种题都需要用递归从root一直到leaves.
: 而且求depth要递归，判断balanced还要递归，最好一次递归就把所需要的值都存下来
: 类似的还有那道求树中两结点间最大path那题
: 这是我的code,见笑了
: public boolean isBalanced(TreeNode root) {
|
l*****a
发帖数: 14598 | 7 重新迭带的目的是？
【在 d**********n 的大作中提到】
: 嗯，这样的确方便不少，不过有一个地方还没怎么想清楚，如果重新迭代，subtree的
: Info是会再计算一遍，还是已经存储了呢，是不是开个全局的structure会更省力？
|
g**u
发帖数: 504 | 8 这个方法好，这道题也可以简单点:如果不是balanced,可以 depth=-1;
【在 l*****a 的大作中提到】
: 我的体会是这种题最好定义一个结构
: class Info {
: int depth;
: boolean balanced;
: }
: 来记录当前子树信息，因为这种题都需要用递归从root一直到leaves.
: 而且求depth要递归，判断balanced还要递归，最好一次递归就把所需要的值都存下来
: 类似的还有那道求树中两结点间最大path那题
: 这是我的code,见笑了
: public boolean isBalanced(TreeNode root) {
|
g**u
发帖数: 504 | 9 就是个DFS, 整棵树只遍历一遍的。
【在 d**********n 的大作中提到】
: 嗯，这样的确方便不少，不过有一个地方还没怎么想清楚，如果重新迭代，subtree的
: Info是会再计算一遍，还是已经存储了呢，是不是开个全局的structure会更省力？
|
d**********n
发帖数: 132 | 10 嗯，懂了！谢谢大家，哈哈
【在 g**u 的大作中提到】
: 就是个DFS, 整棵树只遍历一遍的。
|
