二叉树的右视图

199.二叉树的右视图

题意

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

思路一：递归遍历

其实就是找每一层最右边的节点。

先递归右子树，再递归左子树，保证每往下遍历新一层时，第一个访问的一定是最右边的节点。记录当前层的深度，判断当前深度，对应的节点就在右视图中。

代码：

class Solution {
    void dfs(TreeNode root, int depth, List<Integer> ans) {
        if (root == null) return;

        // 如果这层是首次遍历，将节点加入到右视图中
        // 如果不是首次遍历，则depth一定小于ans.size
        if (depth == ans.size()) ans.add(root.val);

        // 先递归右子树，保证首次遍历的一定是最右边的节点
        dfs(root.right, depth + 1, ans);
        dfs(root.left, depth + 1, ans);
    }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, 0, ans);
        return ans;
    }
}

思路二：层序遍历

对二叉树进行层序遍历，每一层都从左到右遍历，将最后访问到的节点加入到右视图中。最后返回即可。

代码：

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) return List.of();
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        
        q.offer(root);
        while (!q.isEmpty()){
            int n = q.size();
            List<Integer> list = new ArrayList<>(n);
            while (n-- > 0){
                TreeNode node = q.poll();
                // 将每层最后一个加入到结果中
                if (n == 0) res.add(node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
        }

        return res;
    }
}