# 543. Diameter of Binary Tree

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mhgcxq02M5-wVSWkroE%2F-Mhi9xAK3qqqH0IM05Uq%2Fimage.png?alt=media\&token=64f01749-649a-4199-b9c3-3de49e278030)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mhgcxq02M5-wVSWkroE%2F-MhiA064ens1F_XKNdeg%2Fimage.png?alt=media\&token=f27f3637-4d09-4dde-b137-6b4f36d5687e)

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**

```java
res = Math.max(res, left + right); // 所以其實多這行爾以, 多一個 global variable: res
```

can refer:

<https://ithelp.ithome.com.tw/articles/10227129>

time: O(n)

space: O(n)

```java
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)

```java
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
```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;
    }
}
```
````