当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.199.Binary Tree Right Side View 二叉树的右视图

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


上一篇 LeetCode.程序员面试金典.0811.Coin 硬币

下一篇 LeetCode.1248.Count Number of Nice Subarrays 统计优美子数组

阅读
评论
300
阅读预计1分钟
创建日期 2020-04-22
修改日期 2020-04-22
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论