Simple java 2ms solution


  • 0
    C

    O(n) time, O(h) space, and no ArrayList resize penalty.
    Here is the code:

    public class Solution {
        // A simple data struct to reduce the penalty of ArrayList resize
        class Node {
            int val;
            Node next;
            List<Integer> toList() {
                List<Integer> r = new LinkedList<Integer>();
                Node head = next;
                while (head != null) {>! Spoiler
                    r.add(head.val);
                    head = head.next;
                }
                return r;
            }
    
        }
        
        void rightSide(Node node, TreeNode root) {
            if (root != null) {
                // prepare for next level
                if (node.next == null) {
                    node.next = new Node();
                }
                
                // update the val
                node.next.val = root.val;
                rightSide(node.next, root.left);
                rightSide(node.next, root.right);
            }
        }
        public List<Integer> rightSideView(TreeNode root) {
            Node node = new Node();
            rightSide(node, root);
            return node.toList();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.