从右边看二叉树

原题

　　Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
　　For example:
　　Given the following binary tree,

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

　　You should return [1, 3, 4].

题目大意

　　给定一个二叉树&＃xff0c;想象自己站在树的右边&＃xff0c;返回从下到下你能看到的节点的值。

解题思路

　　二叉树的层次遍历&＃xff0c;每层按照从左向右的顺序依次访问节点&＃xff0c;&＃xff08;每一层取最右边的结点&＃xff09;

代码实现

树结点类

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val &＃61; x;}
}

算法实现类

public class Solution {public List rightSideView(TreeNode root) {List result &＃61; new LinkedList<>();if (root !&＃61; null) {Deque deque &＃61; new LinkedList<>();// 当前层的结点数int current &＃61; 1;// 下一层的结点数int next &＃61; 0;TreeNode node;deque.addLast(root);while (deque.size() > 0) {// 取第一个结点node &＃61; deque.removeFirst();current--;// 添加非空的左结点if (node.left !&＃61; null) {next&＃43;&＃43;;deque.addLast(node.left);}// 添加非空的右结点if (node.right !&＃61; null) {next&＃43;&＃43;;deque.addLast(node.right);}// 如果当前层已经处理完了if (current &＃61;&＃61; 0) {// 保存此层的最右一个结点值result.add(node.val);// 设置下一层的元素个数current &＃61; next;next &＃61; 0;}}}return result;}
}