Simple Java Solution. O(n) time complexity and O(depth) space


  • 0
    public class Solution {
        List<Integer> l = new ArrayList<Integer>();
        public List<Integer> rightSideView(TreeNode root) {
            helper(root,0);
            return l;
        }
        
        public void helper(TreeNode root, int index) {
            if (root != null) {
                if (l.size() <= index) {
                    l.add(root.val);
                } else {
                    l.set(index, root.val);
                }
                helper(root.left, index + 1);
                helper(root.right, index + 1);
            }
        }
    }

  • 0
    Z

    I think it is O(depth) space complexity, if you ignore the space took by result list.
    Since it can has at most O(depth) call stacks at a time.


  • 0

    O(max depth) space...


  • 0
    N

    @zehua2 Actually no, the stack space has been allocated when the thread is started. No matter you use it or not, it has been allocated, so we can say that the recursion itself use O(1) space. In Java, the Space complexity should refer to the heap space.


  • 0
    Z

    @nightcatzhou the stack space has been allocated when the thread is started.: As I know, each time you go deeper, you need more stacks.
    For example, suppose you have this function:

    public int foo(int x) {
        if(x == 0) return 0;
        return foo(x-1) - 10;
    }
    

    When you call foo(100) or foo(0), their stack depths are different, the former one needs at least 101 more depth call stacks, while the latter one only needs 1 more call stack.

    The former one's call stack would look like:

    ...
    main()
    foo(100)
    foo(99)
    foo(98)
    ...
    foo(0)
    

    While the latter one:

    ...
    main()
    foo(0)
    

  • 0
    N

    @zehua2 I know what you mean. I am not sure I am correct, because actually I don't have too much knowledge in JVM. But in my understanding, the stack space for a thread is allocated when the thread was started. For example, the thread has 1 MB private memory space for itself. When we make the recursion, the recursion frame will be store in the private memory space of the thread. So it make no memory be allocated, means O(1) space used.


  • 0
    Z

    @nightcatzhou Suppose one call stack need 1 KB, then what about 10,000 calls? One only need one call stack, while another need 10 MB.


  • 0

    @nightcatzhou, I'm on @zehua2. Stack space should also be considered.

    If you have learned OS, you should know heap and stack are just abstraction in different area of virtual memory for a process (in linux, thread is regular process too, instead of light weight process). In other words, what you called private space is also based on abstraction model above, just a buzzword, why you use to buff other people?

    The second difference is the storage duration. The stack is automatic duration, meaning the end of the function. While heap is dynamic duration, depending on runtime. There's also a static duration, aka file duration, which persists till the termination of the program. And these virtual memory should be mapped to real physical space, and should be considered for a program.

    If @nightcatzhou think stack space should not be considered, I appreciate your thinking, :)

    Don't argue on this anymore, O(1) space is just used by the person who posted this to trap other people. Notice of your arguments is kind of :)


  • 0
    C
    thank you share your code. I think '''l.set(index,root.val) ''' is unnecessary.It can be deleted!

  • 0
    T

    My apologies, I wasn't counting the result (which is O(depth) roughly) as part of the space complexity. I've changed the title.


  • 0
    T

    @coldWind I believe I used the set to replace the value in the list, otherwise I would just keep adding when we were on the same depth level which I think is incorrect.


Log in to reply
 

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