LeetCode.199.Binary Tree Right Side View 二叉树的右视图

题目描述

199 Binary Tree Right Side View https://leetcode-cn.com/problems/binary-tree-right-side-view/ 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.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

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

解题过程

层次遍历/广度优先搜索BFS

层次遍历二叉树，记录每一层的最右侧结点即可。

时间复杂度O(n)，空间复杂度O(n)

private static class SolutionV2020 {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (null == root) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelCount = queue.size();
            TreeNode treeNode = new TreeNode(0);
            for (int i = 0; i < levelCount; i++) {
                treeNode = queue.poll();
                if (treeNode.left != null) {
                    queue.offer(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.offer(treeNode.right);
                }
            }
            // 层次遍历每层的最后一个节点
            res.add(treeNode.val);
        }
        return res;
    }
}

根-右-左DFS

按照 根-右-左 的顺序 DFS 遍历，每层最右侧结点首先被访问，dfs 递归方法中要能识别出每个 depth 深度上的第一个被访问结点，是第一个时加入 res 结果集，否则继续访问。

GitHub代码

algorithms/leetcode/leetcode/_199_BinaryTreeRightSideView.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_199_BinaryTreeRightSideView.java