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.
idea:
For every node, length of longest path which pass it= MaxDepth of its left subtree + MaxDepth of its right subtree.
重點是 every node, 所以跟 104 不大一樣的點是, 104 也是求最大深度, 但這是整個的最大深度, 而這題是要最長的左深度 + 右深度, 所以在運算過程中, 要記錄最大的 left + right, 也就是可能不會經過 root, 就有最大diameter了
104 那種整個跑完, 求得整個樹的深度, 一定有經過 root
res = Math.max(res, left + right); // 所以其實多這行爾以, 多一個 global variable: res
can refer:
time: O(n)
space: O(n)
class Solution {
int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxLength(root);
return res;
}
private int maxLength(TreeNode root) {
if (root == null) return 0;
int left = maxLength(root.left);
int right = maxLength(root.right);
res = Math.max(res, left + right); // maybe not walk through root, so record here again
return Math.max(left, right) + 1; // walk through root
}
}
new ver
naive, we can do bfs on each node: O(n^2)
right ver, dfs
T: O(n)
S: O(h), worst O(n)
class Solution {
int numOfNodes = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return numOfNodes-1; // len is num of nodes - 1
}
private int dfs(TreeNode node) {
if (node == null) {
return 0;
}
int left = dfs(node.left);
int right = dfs(node.right);
// res = left side node num + right side node num + node itself
numOfNodes = Math.max(numOfNodes, left+right+1);
// one side's longer length(node num) + node itself
return Math.max(left, right)+1;
}
}
without global variable
```java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
length of the diameter of the tree = max (left depth + right depth)
*/
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
int[] result = new int[1];
dfs(root, result);
return result[0];
}
private int dfs(TreeNode node, int[] result) {
if (node == null) {
return 0;
}
int left = dfs(node.left, result);
int right = dfs(node.right, result);
result[0] = Math.max(result[0], left + right);
return Math.max(left, right) + 1;
}
}
```
