
问题
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
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.
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its depth = 3.
示例
public class Program { public static void Main(string[] args) { var root = new TreeNode(1) { left = new TreeNode(2), right = new TreeNode(3) }; var res = MaxDepth(root); Console.WriteLine(res); res = MaxDepth2(root); Console.WriteLine(res); Console.ReadKey(); } public static int MaxDepth(TreeNode root) { //递归法,本示例无法使用尾递归 if(root == null) return 0; var left = MaxDepth(root.left); var right = MaxDepth(root.right); return Math.Max(left, right) + 1; } public static int MaxDepth2(TreeNode root) { //若为空,返回 0 if(root == null) return 0; //定义结果 var res = 0; //定义一个栈,存一个键值对,键为节点,值为节点的深度 var stack = new Stack<KeyValuePair<TreeNode, int>>(); //把根节点压入栈中,其深度为 1 stack.Push(new KeyValuePair<TreeNode, int>(root, 1)); //处理栈,条件为栈不为空,即当栈空时终止 while(stack.Any()) { //弹出栈顶元素所记录 var top = stack.Pop(); //每次比较最大值并存入 res res = Math.Max(res, top.Value); //为左、右子节点的深度计数 if(top.Key.left != null) { //若左子节点不为空,则将左子节点压入栈中,并将其深度值 +1 stack.Push(new KeyValuePair<TreeNode, int>(top.Key.left, top.Value + 1)); } if(top.Key.right != null) { //若右子节点不为空,则将右子节点压入栈中,并将其深度值 +1 stack.Push(new KeyValuePair<TreeNode, int>(top.Key.right, top.Value + 1)); } } //返回 res return res; } public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } } }
以上给出2种算法实现,以下是这个案例的输出结果:
2 2
分析:
显而易见,以上2种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4072。