二叉树的右视图（199）

题目

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例

输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4] 解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

算法

广度优先遍历

右视图的元素就是广度优先遍历的每一层的末尾元素

export const rightSideView = (root) => {
	if (!root) return [];
	const views = [];
	const queue = [root];
	while (queue.length) {
		const size = queue.length;
		let curNode;
		for (let i = 0; i < size; i++) {
			curNode = queue.shift();
			if (curNode.left) queue.push(curNode.left);
			if (curNode.right) queue.push(curNode.right);
		}
		views.push(curNode.val);
	}
	return views;
};

深度优先遍历

按照根节点 -> 右子树 -> 左子树的顺序访问，维护一个数组res，数组下标就是当前深度，每次遍历到的节点的深度如果在res中不存在的话，那么这个节点一定是这一层的最右边的节点，我们把它写入到结果数组res的对应位置

export const rightSideView = (root) => {
	const res = [];
	let depth = 0;
	const dfs = (node, depth) => {
		if (!node) return node;
		if (!res[depth]) {
			res[depth] = node.val;
		}
		dfs(node.right, depth + 1);
		dfs(node.left, depth + 1);
	};
	dfs(root, depth);
	return res;
};