| 日期 |
是否一次通过 |
comment |
| 2019-01-18 23:13 |
否 |
maxDepth的扩展。理解好“分治”，左子树、右子树 |
| 2019-01-19 20:34 |
Y |
对maxDepth理解加深 |
image.png
- 非递归方法：TODO；
- 递归方法：
2.1 递归思想：不停的分治，result=左子树最大深度+ 右字数最大深度，于是题目转化成为“求最大树的最大深度，同时记录最大的左子树和右子树最大深度之和”
1. 非递归
2.1 递归
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
if(root == null) {
return 0;
}
int[] rst = new int[]{0};
helper(root, rst);
return rst[0];
}
private int helper(TreeNode root, int[] rst) {
if(root == null) {
return 0;
}
int leftDpt = helper(root.left, rst);
int rightDpt = helper(root.right, rst);
rst[0] = Math.max(rst[0], leftDpt+rightDpt);
return Math.max(leftDpt, rightDpt) + 1;
}
}