二叉树最大深度（广度优先bfs、深度优先dfs 两种思路实现）_广度优先求深度

描述：求给定二叉树的最大深度

深度是指树的根节点到任一叶子节点路径上节点的数量。

最大深度是所有叶子节点的深度的最大值。

一、广度优先思路实现（bfs）

通过队列实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 一层一层遍历二叉树 并存入到队列中，然后每遍历一层让count++；
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
        if(root==null){
            return 0;
        }
        ArrayDeque<TreeNode> deque=new ArrayDeque<TreeNode>();
        int count=0;
        deque.add(root);
        while(!deque.isEmpty()){
            count++;		
            int n=deque.size();
            for(int i=0;i<n;i++){ //遍历当前层，把下一层加入到队列中
                TreeNode treeNode=deque.poll();
                if(treeNode.left!=null){
                    deque.add(treeNode.left);
                }
                if(treeNode.right!=null){
                    deque.add(treeNode.right);
                }
                
            }
        }
        return count;
        
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

二、深度优先思路实现（dfs）

通过两个栈实现，同时出栈，同时入栈。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 搭配两个栈实现，一个栈存节点、一个栈存当前节点的所在层数
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
        if(root==null)
            return 0;
        Stack<TreeNode> stackNode=new Stack<TreeNode>();
        Stack<Integer> stackCount=new Stack<Integer>();
        stackNode.push(root);
        stackCount.push(1);
        int max=0;
        while(!stackNode.isEmpty()){
            
            int temp=stackCount.pop();
            TreeNode tree=stackNode.pop(); //一直取最后存入的，即先完成一个分支的深度遍历 
            if(temp>max){
                max=temp; //保证max存入的一直是最大的层数深度
            }
            
            if(tree.left!=null){
                stackNode.push(tree.left);
                stackCount.push(temp+1);
            }
            if(tree.right!=null){
                stackNode.push(tree.right);
                stackCount.push(temp+1);
            }
            
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47