543. Diameter of Binary 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.

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:

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

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