题⽬描述
输⼊⼀棵⼆叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的⼀条路径，最⻓路径的⻓度为树的深度。
示例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 。代码超级⽆敌短：
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null) return 0;
return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
}
}
以上解法要是看不明白，可以看详细点的：
public class Solution {
public int TreeDepth(TreeNode root) {
// 递归终止条件：空节点深度为0
if (root == null) {
return 0;
}
// 递归计算左子树深度
int leftDepth = maxDepth(root.left);
// 递归计算右子树深度
int rightDepth = maxDepth(root.right);
// 当前树深度 = 左右子树最大深度 + 1（当前节点）
return Math.max(leftDepth, rightDepth) + 1;
}
}
- 时间复杂度：O(n)，需要访问每个节点一次
- 空间复杂度：O(h)，递归栈深度等于树高，最坏情况（链表）为O(n)
迭代遍历
思路是如果树的根节点不为空，则将根节点放进队列中。也就是，每遍历一层，深度加1，直到遍历完所有层
设置深度 deep 为0。使⽤ while 循环，只要队列不为空，则执⾏下⾯操作：
- 获取队列的⼤⼩ size 。
- 依次取出队列的前 size 个元素，如果该元素的左边节点不为空，则将左边节点放进队列，如果该元素的右边节点不为空，则将该元素的右边节点放进队列。
- 层次 deep+1
public class Solution {
public int TreeDepth(TreeNode root) {
if (root == null) return 0;
Queue queue = new LinkedList();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()) {
// 当前层的节点个数
int levelSize = queue.size();
// 遍历当前层的所有节点
for (int i = 0; i < levelSize; i++) {
TreeNode currentNode = queue.poll();
// 将下一层节点加入队列
if (currentNode.left != null) {
queue.offer(currentNode.left);
}
if (currentNode.right != null) {
queue.offer(currentNode.right);
}
}
// 完成一层遍历，深度加1
depth++;
}
return depth;
}
}
- 时间复杂度为：O(n)，所有的节点需要进⼊队列，再出队列
- 空间复杂度：O(n),借助了额外的队列空间。
