面试算法46：二叉树的右侧视图

题目

给定一棵二叉树，如果站在该二叉树的右侧，那么从上到下看到的节点构成二叉树的右侧视图。例如，图7.6中二叉树的右侧视图包含节点8、节点10和节点7。请写一个函数返回二叉树的右侧视图节点的值。

分析

既然这个题目和二叉树的层相关，因此可以应用广度优先搜索来解决。由于需要区分二叉树不同的层，因此在遍历时把不同层的节点放入不同的队列，也就是利用两个队列分别存放当前遍历的层和下一层的节点。

解

public class Test {public static void main(String[] args) {TreeNode node8 = new TreeNode(8);TreeNode node6 = new TreeNode(6);TreeNode node10 = new TreeNode(10);TreeNode node5 = new TreeNode(5);TreeNode node7 = new TreeNode(7);node8.left = node6;node8.right = node10;node6.left = node5;node6.right = node7;List<Integer> result = rightSideView(node8);System.out.println(result);}public static List<Integer> rightSideView(TreeNode root) {List<Integer> view = new LinkedList<>();if (root == null) {return view;}Queue<TreeNode> queue1 = new LinkedList<>();Queue<TreeNode> queue2 = new LinkedList<>();queue1.offer(root);while (!queue1.isEmpty()) {TreeNode node = queue1.poll();if (node.left != null) {queue2.offer(node.left);}if (node.right != null) {queue2.offer(node.right);}if (queue1.isEmpty()) {view.add(node.val);queue1 = queue2;queue2 = new LinkedList<>();}}return view;}
}