# 104. Maximum Depth of Binary Tree

### Leetcode

<https://leetcode.com/problems/maximum-depth-of-binary-tree/>

### 題目

Given the `root` of a binary tree, return *its maximum depth*.

A binary tree's **maximum depth** is the number of nodes along the longest path from the root node down to the farthest leaf node.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/11/26/tmp-tree.jpg)

```
Input: root = [3,9,20,null,null,15,7]
Output: 3
```

**Example 2:**

```
Input: root = [1,null,2]
Output: 2
```

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

Recursion (DFS)

```
var maxDepth = function(root) {
    if(!root) return 0;
    
    const children = [root.left, root.right];
    if(children.every(child => !child)) {
        return 1;
    }
    
    let depth = 0;
    children.forEach(child => {
        depth = Math.max(depth, maxDepth(child));
    })
    
    return depth + 1;
};
```

Runtime: 80 ms, faster than 73.62% of JavaScript online submissions for Maximum Depth of Binary Tree.

Memory Usage: 47.3 MB, less than 5.07% of JavaScript online submissions for Maximum Depth of Binary Tree.

* **方法二**

Recursion (DFS)

比較左右兩邊子樹的高度，取其最高再加上本身的高度 1

```
var maxDepth = function(root) {
    if (!root) return 0;
    
    const leftH = maxDepth(root.left);
    const rightH = maxDepth(root.right);
    
    return Math.max(leftH, rightH) + 1;
};
```

Runtime: 91 ms, faster than 57.09% of JavaScript online submissions for Maximum Depth of Binary Tree.

Memory Usage: 44.8 MB, less than 83.64% of JavaScript online submissions for Maximum Depth of Binary Tree.

* **方法三**

Recursion (DFS) - 尾遞歸

方法二的優化

```
var maxDepth = function(root) {
    const helper = (node, totalDepth) => {
        if (!node) return totalDepth;
        const leftH = helper(node.left, totalDepth + 1);
        const rightH = helper(node.right, totalDepth + 1);
        
        return Math.max(leftH, rightH);
    }
    
    return helper(root, 0);
};
```

Runtime: 72 ms, faster than 86.13% of JavaScript online submissions for Maximum Depth of Binary Tree.

Memory Usage: 45.1 MB, less than 68.36% of JavaScript online submissions for Maximum Depth of Binary Tree.

* **方法四**

Iteration (DFS)

```
var maxDepth = function(root) {
    if(!root) return 0;
    
    let ans = 0;
    const stack = [{
        node: root,
        depth: 1
    }]
    while (stack.length) {
        const curr = stack.pop();
        const node = curr.node;
        const depth = curr.depth;
        
        const children = [node.left, node.right];
        if(children.every(child => !child)) {
            ans = Math.max(ans, depth)
        }
        children.forEach(child => {
            if(child) {
                stack.push({
                    node: child,
                    depth: depth + 1
                })
            }
        })
    }
    
    return ans;
};
```

Runtime: 76 ms, faster than 78.84% of JavaScript online submissions for Maximum Depth of Binary Tree.

Memory Usage: 46.8 MB, less than 5.07% of JavaScript online submissions for Maximum Depth of Binary Tree.

* **方法五**

Iteration (BFS)

```
var maxDepth = function(root) {
    if (!root) return 0;
    
    let ans = 0;
    const queue = [{
        node: root,
        depth: 1
    }];
    
    while(queue.length) {
        const curr = queue.shift();
        const node = curr.node;
        const depth = curr.depth;
        
        const children = [node.left, node.right];
        if(children.every(child => !child)) {
            ans = Math.max(ans, depth);
        }
        children.forEach(child => {
            if(child) queue.push({
                node: child,
                depth: depth + 1
            })
        })
    }
    
    return ans;
};
```

Runtime: 84 ms, faster than 68.47% of JavaScript online submissions for Maximum Depth of Binary Tree.

Memory Usage: 46.6 MB, less than 5.49% of JavaScript online submissions for Maximum Depth of Binary Tree.
