C#实现二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

该题和二叉树的层遍历有相似之处，稍做修改即可。

直接附代码

  public static int MaxDepth(TreeNode root)
        {
            //如果树为空 返回0
            if (root == null)
                return 0;
            //定义队列  存储当前层的所有节点
            Queue<TreeNode> queue = new Queue<TreeNode>();
            //把当前根节点加入队列
            queue.Enqueue(root);
            //用于记录深度  就是层数
            int level = 0;
            
            while (queue.Count!=0)
            {
                //记录当前深度
                level++;
                //记录当前层的节点数
                int currentLevelSize = queue.Count;
                //遍历当前层的所有节点
                for (int i = 1; i <= currentLevelSize; i++)
                {   
                    //取出在队列中的头节点  并删除
                    TreeNode node = queue.Dequeue();
                    //看当前节点的左节点是否有值
                    if (node.left != null)
                        queue.Enqueue(node.left);
                    //看当前节点的右节点是否有值
                    if (node.right != null)
                        queue.Enqueue(node.right);
                }
             
            }

            
            return level;




        }
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

这里附上所有代码

using System;
using System.Collections.Generic;

namespace _104._二叉树的最大深度
{
    class Program
    {
        static void Main(string[] args)
        {
            TreeNode tree = new TreeNode()
            {
                val = 1,
                left = new TreeNode()
                {
                    val = 2,
                    left = new TreeNode()
                    {
                        val = 4,
                        left = new TreeNode()
                        {
                            val = 5,
                            left = new TreeNode()
                            {
                                val = 6,

                            }
                        },
                        right = new TreeNode()
                        {
                            val = 7,
                            left = new TreeNode()
                            {
                                val = 8

                            },
                            right = null
                        }
                    },
                    right = null
                },
                right = new TreeNode()
                {
                    val = 9,
                    left = new TreeNode()
                    {
                        val = 10,
                        left = new TreeNode()
                        {
                            val = 11,
                            left = new TreeNode()
                            {
                                val = 12,

                            }
                        },
                        right = new TreeNode()
                        {
                            val = 13,
                            left = new TreeNode()
                            {
                                val = 14

                            },
                            right = null
                        }
                    }


                }
            };

            Console.WriteLine(MaxDepth(tree));
            Console.Read();

        }
        public static int MaxDepth(TreeNode root)
        {
            //如果树为空 返回0
            if (root == null)
                return 0;
            //定义队列  存储当前层的所有节点
            Queue<TreeNode> queue = new Queue<TreeNode>();
            //把当前根节点加入队列
            queue.Enqueue(root);
            //用于记录深度  就是层数
            int level = 0;
            
            while (queue.Count!=0)
            {
                //记录当前深度
                level++;
                //记录当前层的节点数
                int currentLevelSize = queue.Count;
                //遍历当前层的所有节点
                for (int i = 1; i <= currentLevelSize; i++)
                {   
                    //取出在队列中的头节点  并删除
                    TreeNode node = queue.Dequeue();
                    //看当前节点的左节点是否有值
                    if (node.left != null)
                        queue.Enqueue(node.left);
                    //看当前节点的右节点是否有值
                    if (node.right != null)
                        queue.Enqueue(node.right);
                }
             
            }

            
            return level;




        }

        public class TreeNode
        {
            public int val { get; set; }

            public TreeNode left { get; set; }

            public TreeNode right { get; set; }

        }
    }
}

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

顺便把层遍历的代码也写一下：

   public static IList<IList<int>> levelOrder(TreeNode root)
        {
            IList<IList<int>> ret = new List<IList<int>>();
            if (root == null)
            {
                return ret;
            }

            Queue<TreeNode> queue = new Queue<TreeNode>();
            queue.Enqueue(root);
            while (queue.Count!=0)
            {
                List<int> level = new List<int>();
                int currentLevelSize = queue.Count;
                for (int i = 1; i <= currentLevelSize; ++i)
                {
                    TreeNode node = queue.Dequeue();
                    level.Add(node.val);
                    if (node.left != null)
                    {
                        queue.Enqueue(node.left);
                    }
                    if (node.right != null)
                    {
                        queue.Enqueue(node.right);
                    }
                }
                ret.Add(level);
            }

            return ret;
        }
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

好了，持续更新…