題目描述

??給定一個二叉樹的 根節(jié)點 root，想象自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節(jié)點值。

解析

??這一題的關鍵其實就是找到怎么去得到當前是哪一層級，可以利用隊列對二叉樹進行層次遍歷，但是需要稍微修改下遍歷方式，每次都將該層遍歷完。

public List<Integer> rightSideView(TreeNode root) {if (root == null) {return new ArrayList<>();  // 返回空列表而非null}List<Integer> res = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int levelLength = queue.size();  // 當前層的長度for (int i = 0; i < levelLength; i++) {TreeNode node = queue.poll();// 僅在遍歷到當前層最后一個元素時記錄if (i == levelLength - 1) {res.add(node.val);}if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}return res;}

??然后深度優(yōu)先遍歷也是可以求解。優(yōu)先遍歷右子樹，同時記錄下當前遍歷到的層級即可。

public List<Integer> rightSideView(TreeNode root) {List<Integer> ans = new ArrayList<>();dfs(root, 0, ans);return ans;}private void dfs(TreeNode node, int depth, List<Integer> ans) {if (node == null) {return;}if (ans.size() == depth) {ans.add(node.val);}depth++;dfs(node.right, depth, ans);dfs(node.left, depth, ans);}