題目描述

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

解析

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

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();  // 當(dāng)前層的長(zhǎng)度f(wàn)or (int i = 0; i < levelLength; i++) {TreeNode node = queue.poll();// 僅在遍歷到當(dāng)前層最后一個(gè)元素時(shí)記錄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)先遍歷右子樹(shù)，同時(shí)記錄下當(dāng)前遍歷到的層級(jí)即可。

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);}