【1错-1】是否平衡二叉树
2019-01-27 本文已影响1人
7ccc099f4608
| 日期 | 是否一次通过 | comment |
|---|---|---|
| 2019-01-27 20:20 | N | 1. 对maxDepth理解不深：maxDepth是不停的分治，判断左右子树最大深度（postOrder），而不是累加；2. maxDepth在本题中复杂度太高，相当于每个子树都得算独立的深度，不科学 |
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
1. 原版maxDepth
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null) {
return true;
}
if(Math.abs(helper(root.left) - helper(root.right)) > 1) {
return false;
}
return true;
}
private int helper(TreeNode root) {
if(root == null) {
return 0;
}
return Math.max(helper(root.left), helper(root.right)) + 1;
}
}
2. 调整后的maxDepth
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
return helper(root) != -1;
}
private int helper(TreeNode root) {
if(root == null) {
return 0;
}
int leftDpt = helper(root.left);
int rightDpt = helper(root.right);
if(leftDpt == -1 || rightDpt == -1 || Math.abs(leftDpt - rightDpt) > 1) {
return -1;
}
return Math.max(leftDpt, rightDpt) + 1;
}
}
