剑指offer-38、⼆叉树的深度

题⽬形貌

输⼊⼀棵⼆叉树，求该树的深度。从根结点到叶结点依次颠末的结点（含根、叶结点）形成树的⼀条路径，最⻓路径的⻓度为树的深度。
示例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 。代码超等⽆敌短：

1. public class Solution {
2.      public int TreeDepth(TreeNode root) {
3.          if(root==null) return 0;
4.          return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
5.      }
6. }

复制代码

以上解法要是看不明确，可以看具体点的：

1. public class Solution {
2.     public int TreeDepth(TreeNode root) {
3.         // 递归终止条件：空节点深度为0
4.         if (root == null) {
5.             return 0;
6.         }
7.         
8.         // 递归计算左子树深度
9.         int leftDepth = maxDepth(root.left);
10.         // 递归计算右子树深度
11.         int rightDepth = maxDepth(root.right);
12.         
13.         // 当前树深度 = 左右子树最大深度 + 1（当前节点）
14.         return Math.max(leftDepth, rightDepth) + 1;
15.     }
16. }

复制代码

• 时间复杂度：O(n)，须要访问每个节点一次
  
• 空间复杂度：O(h)，递归栈深度即是树高，最坏情况（链表）为O(n)
  

迭代遍历

思绪是如果树的根节点不为空，则将根节点放进队列中。也就是，每遍历一层，深度加1，直到遍历完全部层
设置深度 deep 为0。使⽤ while 循环，只要队列不为空，则执⾏下⾯利用：

• 获取队列的⼤⼩ size 。
  
• 依次取出队列的前 size 个元素，如果该元素的左边节点不为空，则将左边节点放进队列，如果该元素的右边节点不为空，则将该元素的右边节点放进队列。
  
• 条理 deep+1
  

1. public class Solution {
2.     public int TreeDepth(TreeNode root) {
3.         if (root == null) return 0;
4.         
5.         Queue<TreeNode> queue = new LinkedList<>();
6.         queue.offer(root);
7.         int depth = 0;
8.         
9.         while (!queue.isEmpty()) {
10.             // 当前层的节点个数
11.             int levelSize = queue.size();
12.             
13.             // 遍历当前层的所有节点
14.             for (int i = 0; i < levelSize; i++) {
15.                 TreeNode currentNode = queue.poll();
16.                
17.                 // 将下一层节点加入队列
18.                 if (currentNode.left != null) {
19.                     queue.offer(currentNode.left);
20.                 }
21.                 if (currentNode.right != null) {
22.                     queue.offer(currentNode.right);
23.                 }
24.             }
25.             
26.             // 完成一层遍历，深度加1
27.             depth++;
28.         }
29.         
30.         return depth;
31.     }
32. }

复制代码

• 时间复杂度为：O(n)，全部的节点须要进⼊队列，再出队列
  
• 空间复杂度：O(n),借助了额外的队列空间。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。