DFS VS BFS
题目
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
// DFS 解题
var rightSideView = function(root) {
let resultList = []
let i = 0
let dfs = function (Node, i) {
// 该节点不存在
if (!Node) {
return
}
resultList[i] = resultList[i] || []
resultList[i].push(Node.val)
dfs(Node.left, i + 1)
dfs(Node.right, i + 1)
}
dfs(root, i)
return resultList.map(result => result[result.length - 1])
};
// 优先左子树，再遍历右子树，每次递归深度+1
// BFS 解题
var rightSideView = function(root) {
let resultList = []
let j = -1
let bfs = function (Nodes) {
while (Nodes.length > 0) {
j++
// 该节点不存在
if (!Nodes.length) {
return
}
let length = Nodes.length
for (let i = 0; i < length; i++) {
let Node = Nodes.shift()
resultList[j] = resultList[j] || []
resultList[j].push(Node.val)
if (Node.left) Nodes.push(Node.left)
if (Node.right) Nodes.push(Node.right)
}
}
}
if (!root) return []
bfs([root])
return resultList.map(result => result[result.length - 1])
};
// 广度优先遍历的核心就是queues
// 队列存储左右节点，然后进入下一次循环，循环原始队列，队列头出队列，将左子树右子树分别重新插入队列，最后的到的类似[left.left, left.right, right.left, right.right]进行我们想要的操作