LeetCode 题解-104. maximum depth of binary tree

对Leetcode 104. maximum depth of binary tree 题目的求解。

Problem Description#

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example#

Example 1

1
Given binary tree [3,9,20,null,null,15,7], return its depth = 3.

Solution 1: Iterative solution#

这道题目的描述很符合递归算法的特征，而树又是非常适合递归算法的数据结构，因此我们很容易写出两行的代码。需要注意的只有对空节点的判断。

1
class Solution {
2
    public int maxDepth(TreeNode root) {
3
        if (root == null) return 0;
4
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
5
    }
6
}

想要知道树的最大深度，我们只需要进行一次遍历即可。事实上，深度优先和宽度优先的算法都适用与此题。

Solution 2#

深度有限遍历。

1
class Solution {
2
    public int maxDepth(TreeNode root) {
3
        if (root == null) return 0;
4
        Stack<TreeNode> s= new Stack<TreeNode>();
5
        Stack<Integer> ss= new Stack<Integer>();
6
        s.push(root);
7
        ss.push(1);
8
        int max = 0;
9
        while (!s.isEmpty()){
10
            TreeNode n = s.pop();
11
            int d = ss.pop();
12
            max = Math.max(d, max);
13
            if (n.left != null){
14
                s.push(n.left);
15
                ss.push(d+1);
16
            }
17
            if (n.right != null){
18
                s.push(n.right);
19
                ss.push(d+1);
20
            }
21
        }
22
        return max;
23
}

Solution 3#

宽度优先遍历

1
public int maxDepth(TreeNode root) {
2
        if (root == null) return 0;
3
        Queue<TreeNode> q = new LinkedList<TreeNode>();
4
        Queue<Integer> qq = new LinkedList<Integer>();
5
        q.add(root);
6
        qq.add(1);
7
        int max = 0;
8
        while (!q.isEmpty()){
9
            TreeNode n = q.poll();
10
            int d = qq.poll();
11
            max = Math.max(d, max);
12
            if (n.left != null){
13
                q.add(n.left);
14
                qq.add(d+1);
15
            }
16
            if (n.right != null){
17
                q.add(n.right);
18
                qq.add(d+1);
19
            }
20
        }
21
        return max;
22
    }

Solution 4#

事实上，我们还有一种更有效的遍历求解方法，即层次遍历。

1
    public static int maxDepth(TreeNode root) {
2
        if (root == null) return 0;
3
        Queue<TreeNode> q = new LinkedList<TreeNode>();
4
        q.add(root);
5
        int max = 0;
6
        while (!q.isEmpty()){
7
            int size = q.size();
8
            for (int i = 0; i < size; ++i){
9
                TreeNode tmp = q.poll();
10
                if (tmp.left != null) q.add(tmp.left);
11
                if (tmp.right != null) q.add(tmp.right);
12
            }
13
            max += 1;
14
        }
15
        return max;
16
    }