广度优先遍历 BFS
解题思路
使用 层序遍历 进行遍历，队列里面会放置二叉树每一层的节点；
队列的最后一个节点一定是右视图看到的第一个元素，将最后一个节点放入结果中即可；
复杂度
-
时间复杂度 :
O(n)，每个节点最多进队列一次，出队列一次； -
空间复杂度 :
O(n)，每个节点最多进队列一次，所以队列长度最大不不超过 n；
代码实现
var rightSideView = function (root) {
if (root === null) return [];
const res = [];
const queue = [root]; // 声明队列用于存储后续数据
while (queue.length) {
let len = queue.length;
while (len--) {
const node = queue.shift();
// 由于每一层最后一个访问到的节点才是答案，因此不断更新对应深度的信息即可
if (len === 0) res.push(node.val);
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
return res;
};
深度优先遍历 DFS
解题思路
先递归访问右子树，再递归访问左子树，递归左子树的原因是，有可能左子树的高度更高，这样可以保证每层都是最先访问最右边的节点；
当前节点是否需要放入结果呢？记录当前节点的深度，如果
当前节点深度 === 结果数组长度说明该节点在次层级是第一个被访问的节点，则将当前节点加入 res 中（利用 结果数组长度 可以过滤掉同层级的左节点）；
图解
复杂度
-
时间复杂度 :
O(n)，深度优先搜索最多访问每个结点一次，因此是线性复杂度； -
空间复杂度 :
O(n)，因为这不是一棵平衡二叉树，二叉树的深度最少是0(logN)，最坏的情况下会退化成一条链表，深度就是 N ，因此递归时使用的栈空间是O(N)；
代码实现
var rightSideView = (root) => {
const res = [];
dfs(res, root, 0); // 从根节点开始访问，根节点深度是 0
return res;
};
const dfs = (res, root, depth) => {
if (root === null) return;
// 1. 先访问当前根节点，如果当前节点所在深度 === res.length，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入 res 中
if (depth === res.length) res.push(root.val);
// 2. 递归地访问右子树、左子树
depth++;
dfs(res, root.right, depth);
dfs(res, root.left, depth);
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 107. 二叉树的层序遍历Ⅱ
上一篇
评论
