> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/tree/543.-diameter-of-binary-tree.md).

# 543. Diameter of Binary Tree

![](/files/-Mhi9xAK3qqqH0IM05Uq)

![](/files/-MhiA064ens1F_XKNdeg)

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/tree/543.-diameter-of-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.