LeetCode-Questions/LC_199_BinaryTreeRightSideView.java at main · Harshchafle/LeetCode-Questions · GitHub

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
75
76
77
78
79
80
81
82
83
84
/**
 * 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> list = new ArrayList<>();
        int levels = getLevel(root);
        for(int i = 0; i < levels; i++){
            list.add(0);
        }
        postOrder(root, list, 0);
        return list;
    }

    public int getLevel(TreeNode root){
        if(root == null) return 0;
        return 1+Math.max(getLevel(root.left), getLevel(root.right));
    }

    // PreOrder
    public void preOrder(TreeNode root, List<Integer> list, int level){
        if(root == null)return;
        list.set(level, root.val);
        preOrder(root.left, list, level+1);
        preOrder(root.right, list, level+1);
        return;
    }

    // Inorder
    public void inOrder(TreeNode root, List<Integer> list, int level){
        if(root == null)return;
        inOrder(root.left, list, level+1);
        list.set(level, root.val);
        inOrder(root.right, list, level+1);
        return;
    }

    // PostOrder
    public void postOrder(TreeNode root, List<Integer> list, int level){
        if(root == null)return;
        postOrder(root.left, list, level+1);
        postOrder(root.right, list, level+1);
        list.set(level, root.val);
        return;
    }

    // Level Order
    // public List<Integer> rightSideView(TreeNode root) {
    //     List<Integer> list = new ArrayList<>();
    //     int levels = getLevel(root);
    //     boolean done[] = new boolean[levels];
    //     bfs(root, list, levels, 0, done);
    //     return list;
    // }

    // public int getLevel(TreeNode root){
    //     if(root == null) return 0;
    //     return 1+Math.max(getLevel(root.left), getLevel(root.right));
    // }

    // public void bfs(TreeNode root, List<Integer> list, int levels, int currLevel, boolean[] done){
    //     if(root == null) return;
    //     for(int i = 0; i < levels; i++){
    //         if(!done[currLevel]){
    //             done[currLevel] = true;
    //             list.add(root.val);
    //         }
    //     }
    //     bfs(root.right, list, levels, currLevel+1, done);
    //     bfs(root.left, list, levels, currLevel+1, done);
    // }
}