LeetCode199-二叉树的右视图

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/binary-tree-right-side-view/

中文链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/

题目详述

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

示例:

1
2
3
4
5
6
7
8
9
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

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

题目详解

方法一：BFS。

  • 进行层次遍历。
  • 每进入一层得到该层最右边的结点，加入结果集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class LeetCode_00199 {

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- != 0) {
                TreeNode node = queue.poll();
                if (size == 0) {
                    res.add(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return res;
    }
}

方法二：DFS。

  • 进行层次遍历，采用 DFS 实现。
  • 进入下一层每次先往右子树走。
  • 当结果集的大小等于层数时，添加当前结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_00199 {

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

    private void helper(TreeNode root, List<Integer> res, int level){
        if(root == null) {
            return;
        }
        if(res.size() == level) {
            res.add(root.val);
        }
        // 先往右子树走
        helper(root.right, res, level + 1);
        helper(root.left, res, level + 1);
    }
}