199. Binary Tree Right Side View

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.

1
2
3
4

Example 1:

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

ex1

1
2
3
4

Example 2:

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

1
2
3
4

Example 3:

Input: root = []
Output: []

Constraints:

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

Recursive

jam1

Iterative

jam2

Solution

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/**
 * 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 {
    int head = 0;
    int tail = 0;
    TreeNode[] q = new TreeNode[101];
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return Collections.emptyList();
        add(root);
        while (!isEmpty()) {
            res.add(peek().val);
            int n = size(); // remove prev level
            for (int i = 0; i < n; i++) {
                TreeNode node = poll();
                if (node.right != null) add(node.right);
                if (node.left != null) add(node.left);
            }
        }
        return res;
    }
    
    boolean isEmpty() {
        return tail == head;
    }
    
    int size() {
        return tail - head;
    }
    
    TreeNode poll() {
         if (!isEmpty()) {
            return q[head++];
        }
        throw new RuntimeException();
    }
    
    void add(TreeNode a) {
        q[tail] = a;
        tail++;
    }
    
    TreeNode peek() {
       return q[head];
    }
    
    public List<Integer> rightSideView2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        visit(root, res, 0);
        return res;
    }
    
    void visit(TreeNode node, List<Integer> res, int depth) {
        if (node == null) return;
        if (res.size() == depth) {
            res.add(depth, node.val);
        }
        visit(node.right, res, depth + 1);
        visit(node.left, res, depth + 1);
    }
}

Solution 15-06-2021

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

/**
 * 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 {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> levels = new ArrayList<>();
        dfs(0, root, levels);
        return levels;
    }

    void dfs(int level, TreeNode root, List<Integer> levels) {
        if (root == null) {
           return;
        }
        add(level, root.val, levels); // 2 5
        dfs(level + 1, root.left, levels);
        dfs(level + 1, root.right, levels);
    }


    // 0 1 2 3 4 -> 5
    // []
    void add(int level, int val, List<Integer> levels) {
        // first element on level
        if (levels.size() == level) {
            levels.add(val);
            return;
        }

        // remove previous, add new element
        levels.remove(level);
        levels.add(level, val);
    }

}