[leetcode #199] Binary Tree Right Side View

Problem

Given the root of 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 1:

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

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

Constraints:

· The number of nodes in the tree is in the range [0, 100].
· -100 <= Node.val <= 100

Idea

트리 탐색만 잘 하면 쉬운 문제다.

inorder나 preorder 방식으로 탐색하면 Tree의 오른쪽 노드가 가장 마지막으로 탐색이 된다. 레벨을 재귀함수에 넣어주고 탐색할 때 레벨에 해당하는 노드의 값을 교체하면 오른쪽에서 바라보는 노드의 값으로 설정이 된다.

알고리즘은 다음과 같다.

1. Tree를 inorder나 preorder 방식으로 탐색을 하며, 인자로 Tree의 level을 넣어준다.
2. List의 level 번째 원소를 현재 노드의 값으로 교체한다. level이 리스트의 크기보다 같거나 클 경우 노드의 값을 리스트에 더해준다.
3. 만들어진 List를 리턴한다.

Time Complexity: O(N)
Space Complexity: O(1)

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        traverseTree(root, 0);

        return res;
    }

    private void traverseTree(TreeNode node, int level) {
        if (node == null) {
            return;
        }

        if (res.size() <= level) {
            res.add(node.val);
        }

        res.set(level, node.val);

        traverseTree(node.left, level+1);
        traverseTree(node.right, level+1);
    }
}

Reference

https://leetcode.com/problems/binary-tree-right-side-view/