00-1010给定一棵二叉树，返回它的最大深度。

示例：

一个

/

2 3

//

4 5 6 7

返回的最大深度是3。

问题：求二叉树的最大深度

先用深度或广度遍历二叉树，找到树的最大深度。

解题思路

类型TreeNode结构{

左*TreeNode //左子节点

右*TreeNode //右子节点

价值//价值

}

二叉树的结构体

深度优先搜索

1.深度优先搜索类似于二叉树的前序遍历。

2.使用递归持续探索树的深度。

3.递归的终止条件是，如果节点为空，则返回0。然后判断左右子树的最大值，同时加1表示当前节点的高度。

func MaxDepth(root * TreeNode)int {

//如果节点为空，则不会递归向下钻取深度。

if root==nil {

返回0

}

左：=最大深度(root.left)

右：=maxDepth(root.right)

如果从左向右{

向左返回1

}

向右返回1

}时间复杂度：O(n)，其中n为节点数。因为每个节点都必须被访问一次。

空间复杂度：O(logN)，其中n为节点数。当树不平衡时，空间复杂度为O(N)，例如，当树跛行和左撇子时。但如果树是平衡的，空间复杂度为O(logN)。

00-1010

主要思路

1.广度优先搜索使用迭代将每一层的节点放入队列。

2.队列离开队列，清空到下一层。

3.用变量标记深度。每次输入下一次记录深度时，向该变量添加1。

func MaxDepth(root * TreeNode)int {

//如果根节点为0，则直接返回0。

if root==nil {

返回0

}

队列：=make ([] * treenode，0)//创建队列。

Queue=append(queue，root) //将根节点放入队列中。

深度：=0 //声明一个深度变量

对于len(队列){ 0

//如果队列中有值，循环将继续。

Size :=len(queue) //这里，我们要遍历当前级别的队列，全部出列。

对于I :=0；isize我

v :=队列[0]

队列=队列[1:] //出列

如果v .离开！=零

Queue=append(queue，v.left) //如果有左子树，则左子树将排队。

}

如果v .对！=零

Qu=append (queue，v . right)//如果有右子树，则右子树将被排队。

}

}

深度//清除一个图层后，向变量添加1。

}

返回深度

}时间复杂度：O(n)，n代表节点，每个节点都要遍历一次。

空间复杂度：O(n)，最坏的情况是队列被一层节点填满。

如有错误，请指正并讨论。