- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
DFS 深度优先遍历
按照树的深度将每层对应的节点添加到对应层的数组中即可。
constlevelOrder=function(root){if(!root)return[]constres=[]dfs(root,0,res)returnres};constdfs=function(root,depth,res){if(!root)return// 递归终止条件if(!res[depth])res[depth]=[]res[depth].push(root.val)// 存入每层的节点值dfs(root.left,depth+1,res)// drill downdfs(root.right,depth+1,res)}
BFS 广度优先遍历
根据层次返回其对应的结果集合。
1.边界处理，初始化队列 queue 和存放结果的数组 res。
2.外层循环遍历层级结构，内层循环遍历每一层的子节点。
3.遍历时需要记录当前层的遍历次数 len 以及当前层的节点数组 arr。
4.取得 node 依次出队，并依次存入当前层的节点数组中。
5.若存在左右子节点，则依次入队，并更新 len。
6.遍历完后返回结果 res。
constlevelOrder=function(root){if(!root)return[]constqueue=[root]constres=[]while(queue.length>0){constarr=[]letlen=queue.lengthwhile(len){letnode=queue.shift()arr.push(node.val)if(node.left)queue.push(node.left)if(node.right)queue.push(node.right)len--}res.push(arr)}returnres};
- 时间复杂度: O(n)
- 空间复杂度: O(n)