LeetCode199二叉树的右视图

题目描述

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

解析

  这一题的关键其实就是找到怎么去得到当前是哪一层级，可以利用队列对二叉树进行层次遍历，但是需要稍微修改下遍历方式，每次都将该层遍历完。

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

  然后深度优先遍历也是可以求解。优先遍历右子树，同时记录下当前遍历到的层级即可。

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