题⽬描述

输⼊⼀棵⼆叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的⼀条路径，最⻓路径的⻓度为树的深度。

示例1 输⼊：{1,2,3,4,5,#,6,#,#,7} 返回值：4

思路及解答

声明：这⾥的输⼊是⼀个数的根节点，也就是从根节点，我们就可以获取到树的所有节点，⽽类似数组的表达⽅式 {1,2,3,4,5,#,6,#,#,7}，则是按照层次来放的。(⽐如这个树就是4层)

递归

第⼀种⽅法⽐较容易想到，对于任意⼀个节点 node ⽽⾔，我要想知道当前 node 节点（包括当前节点）的深度，肯定得求当前节点的左边节点（设为 left ）的深度 leftDeepth，以及获取右节点（设为 right ）的深度 rightDeepth，然后求两者最⼤+1（ Max{leftDeepth,rightDeepth}+1 ），就是当前节点的深度。

思路：二叉树的深度 = max(左子树深度, 右子树深度) + 1 ⽽递归中⽐较重要的⼀点，是结束条件。在这道题中，如果⼀个节点为 null，就结束，并且当前节点的深度是 0 。代码超级⽆敌短：

以上解法要是看不明白，可以看详细点的：

  • 时间复杂度：O(n)，需要访问每个节点一次

  • 空间复杂度：O(h)，递归栈深度等于树高，最坏情况（链表）为O(n)

迭代遍历

思路是如果树的根节点不为空，则将根节点放进队列中。也就是，每遍历一层，深度加1，直到遍历完所有层

设置深度 deep 为0。使⽤ while 循环，只要队列不为空，则执⾏下⾯操作：

  1. 获取队列的⼤⼩ size 。

  2. 依次取出队列的前 size 个元素，如果该元素的左边节点不为空，则将左边节点放进队列，如果该元素的右边节点不为空，则将该元素的右边节点放进队列。

  3. 层次 deep+1

  • 时间复杂度为：O(n)，所有的节点需要进⼊队列，再出队列

  • 空间复杂度：O(n),借助了额外的队列空间。