二叉树的深度
题目描述
示例
示例1
js
输入：
{1,2,3,4,5,#,6,#,#,7}
返回值：
4示例2
js
输入：
{}
返回值：
0代码
代码1 深度遍历（分治法，先左后右 挨个遍历一遍，递归）
js
/*
深度遍历，分治法：
求一个规模为n的问题，先求左边规模大约为n/2的问题，再求右边规模大约为n/2的问题，
然后合并左边、右边的解，从而求得最终解。
1. 求 pro(left, rigth) -> int
2. 先求pro(left, (left+right)/2) -> lval
3. 再求pro((left+right)/2 + 1, right) -> rval
4. merge(lval, rval) -> result
最终结果为 max( 头结点左子树的最大深度, 头结点右子树的最大深度)+1
*/
function TreeDepth(pRoot)
{
if(!pRoot) return 0
let lval = TreeDepth(pRoot.left)
let rval = TreeDepth(pRoot.right)
return Math.max(lval, rval) + 1
}时间复杂度为 O(n)：n为遍历的节点数量，计算树的深度时所需要遍历的所有节点
空间复杂度为O(n)：n为递归时需要开辟的额外栈空间，用于递归方法堆栈
代码2 层次遍历（使用队列辅助，先入先出，一层一层的找）
js
/*
层次遍历法：一层一层的遍历，需要使用个队列辅助一下，js中使用数组模拟一下
1. 初始化：一个队列queue<treenode*> q， 将root节点入队列q
2. 如果队列不空，做如下操作：
3. 弹出队列头，保存为node，将node的左右非空孩子加入队列
4. 做2,3步骤，知道队列为空
*/
function TreeDepth(pRoot)
{
if(!pRoot) return null
// 使用数组模拟一个队列
let queue = []
// 根节点入队
queue.push(pRoot)
let height = 0 // 记录深度
// 开始层次遍历
while(queue.length > 0){ // 一层一层的遍历
// 先获取到当前队列中有几个节点（本层节点数）
let size = queue.length
while(size !== 0) { // 遍历该层的节点，没遍历一个 就出队一个，遍历的同时，把他们下一层的节点入队
// 出队（先入先出，因为之前是push进的，所以使用shift出队）
let currentNode = queue.shift()
if(currentNode.left){ // 入队
queue.push(currentNode.left)
}
if(currentNode.right){ // 入队
queue.push(currentNode.right)
}
//每循环一次，当前层的节点数就减一
size--
}
// 里层的循环每次执行完，就表示走完了一层，深度+1
height++
}
return height
}时间复杂度O(n)：n是遍历节点的个数。
空间复杂度O(n)：队列占用的空间。