199. Binary Tree Right Side View

[songyy5517]

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: []

Intuition This problem essentially can be converted into find the last node in each layer in the binary tree. Therefore, a simple idea is to loop through the whole tree with BFS, and then extract the last node of each layer. Besides, we can also use DFS to tackle this problem. In particular, we can apply pre-order travarsal and also define a array list to store the node we meet in each layer. When we encounter a node, we replace the previous node of this layer with the current node. Finally, we can obtain all the rightmost nodes in each layer.

[songyy5517]

Approach: BFS

1. Exception handling;
2. Define variables and initialization:
   • Arraylist res: stores all the rightmost nodes;
   • Queue queue: is used for BFS;
3. Travarse the tree with BFS and extract the last node in each layer into the arraylist;
4. Return the arraylist.

Complexity Analysis

• Time complexity: $O(N)$ , looping through all the nodes in the binary tree takes $O(N)$ time;
• Space complexity: $O(N)$ , additionally define a queue when applying BFS, the maximum number of nodes in the queue would not exceed $N$ , which occupying $O(N)$ space.

[songyy5517]

/**
 * 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 {
    ArrayList<Integer> res = new ArrayList();

    public List<Integer> rightSideView(TreeNode root) {
        // Intuition: The nodes than can be seen are the last node of each layer.
        // So we can travarse the tree layer-wise, and extract each node in each layer.
        // 1. Exception handling
        if (root == null)
            return new ArrayList();

        // 2. Define variables
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);

        // 3. BFS
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++){
                TreeNode cur_Node = queue.remove();
                if (cur_Node.left != null)
                    queue.add(cur_Node.left);

                if (cur_Node.right != null)
                    queue.add(cur_Node.right);

                if (i == size - 1)
                    res.add(cur_Node.val);
            }
        }

        return res;
    }
}

[songyy5517]

2024/6/6