DiameterOfBinaryTree [source code]
public class DiameterOfBinaryTree {
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return max;
}
private int maxDepth(TreeNode root) {
if (root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
max = Math.max(max, left + right);
return Math.max(left, right) + 1;
}
public static void main(String[] args) {
DiameterOfBinaryTree tester = new DiameterOfBinaryTree();
}
}
这个是看的discussion 的最优解, 虽然不是最快的, 但是清晰易懂. 这个问题总体来说我还是放弃的太快了, 感觉自己对于 tree 问题的掌握还是不够深入.
tree 问题最终很多时候还是要依靠 recursion. 这里还是几个切入点:
- 每一个 recursion 的返回值是什么. 这里的这个跟前面做过的一个题目有点类似, 就是recursive return value并不是直接就是你最终要求的东西. 好像 depth 是 tree 问题里面经常利用的一个量? 因为这个确实是很好求的.
- 站在 recursion 的角度, 你看到的, 只是这个 root, 不要想他上面的, 想其他的. 就给了你这个 root, 你希望它拥有什么样的信息? 进一步的, 你希望让 root 怎样利用root.left and root.right能够提供的类似的信息?
虽然很多时候你画了一个很大的 tree, 但是实际上很多时候, 你需要考虑的就三个 node:
root
/ \
left right
站在recursion 的角度, 你要考虑的就是怎样将结果递归的向上传递; - 这一题如果只是知道这几点, 其实最后答案还不是特别清晰. 另外一个需要掌握的切入点就是, recursion 的搜索速度就是 DFS.
如果单纯从第二点的this level的角度出发, 这一题的答案其实是不容易得到的.
在分析这个问题的时候遇到的一个难点在于, 你无法确定 longest 是否经过 root. 如果不经过 root, 那么最后就感觉完全无从下手.
这一题其实每一个 root 要保存两个信息, 一个就是当前 node 的 subtree 的 max depth, 这个就是 recursive call 的返回值; 另外一个就是the length of the longest path that PASSES this root. 注意, 这个 length 还不是 diameter! 按理说这个 length 本身也是要分别存储下来的, per node/root. 但是因为我们这里最后需要的只是一个 max, 所以我们实际上只要维护一个global max buffer, 保持更新就行了.
这个题目的难点是提取出这个 path passing the root 的概念. 如果只是按照最单纯的 DP 的概念, 你很可能先到的就是, length of the longest path in the subtree of this root, 但是这样一个概念在 DP 上是没有意义的: 你没有办法用root.left.diameter and root.right.diameter直接推导出root.diameter, 也就是不满足 DP property. 那么这个时候合理的思路就应该是退而求其次, 找到一个另外的量, 不是直接就是你想要求的这个量, 但是跟其有一定关联. 这里找到的这个量就是length of longest path passing the root. 这个量是满足 DP property 的. 而只要当我们拥有每一个 node 的longest passing之后, 找到整个 tree 的 longest 只要多一步处理就行了.
可以看到, 用 recursion 的思路来理解这个问题相当困难, 想到这个答案可能几乎完全凭感觉和灵光一现.
但是如果用 DFS 的思路来理解(说到底, 这个无非还是就是一个iterating 的过程), 就完全有可能想到这个答案, 因为这个就跟你自己思考historical stream问题一样的, 就是自己走 ierator, 然后总结规律.
当然具体怎么总结出来这个 passing 的概念, 我好像还是不能说的很清楚.
反正好像最后你总结的recursive value(比如这里的max depth and longest passing), 最好能够让 root 参与. 这一题这个要求比较自然就能满足, 因为虽然 path 不一定 pass root, 但是longest path一定是会 pass root的.
这个算法最后的速度倒是比较一般, 只有11(40), 不过还是能够学到很多的东西.
这个是 discussion 上面的另外一个解:
public class Solution {
public int diameterOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
int dia = depth(root.left) + depth(root.right);
int ldia = diameterOfBinaryTree(root.left);
int rdia = diameterOfBinaryTree(root.right);
return Math.max(dia,Math.max(ldia,rdia));
}
public int depth(TreeNode root){
if(root == null){
return 0;
}
return 1+Math.max(depth(root.left), depth(root.right));
}
}
这个解的复杂度是相当差的, 因为他DFS 过程中每一个 node 都要计算一下当前 node 的 depth, 就是 recursion 里面套了一个 recursion. 这里面的重复计算量是相当大的.
回过头看这里的这个最优解, 其实真正用 recurse 来计算的只有 depth. diameter 或者 longest passing 本身并没有依赖 recursion;
submission 最优解是这个:
public class Solution {
public int diameterOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
int[] max = new int[1];
find(root,max);
return max[0];
}
private int find(TreeNode n, int[] max){
if(n == null){
return -1;
}
int left = find(n.left, max)+1;
int right = find(n.right, max)+1;
if(max[0] < left + right){
max [0] = left + right;
}
return Math.max(left, right);
}
}
其实意思是一样的, 不过这里不想用instance variable, 就用 main 里面的一个local temp来做类似 global 的工作. 为了绕过 primitive 的 immutability, 就把这个 max 放在一个array 里面, 这样就可以当一个 mutable 来用了.
Problem Description
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example:
Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.
Difficulty:Easy
Category:Algorithms
Acceptance:43.18%
Contributor: nagasupreeth
Companies
google facebook
Related Topics
tree