Java Solution using Divide and Conquer


  • 21
    M
    public List<Integer> rightSideView(TreeNode root) {
        if(root==null)
            return new ArrayList<Integer>();
        List<Integer> left = rightSideView(root.left);
        List<Integer> right = rightSideView(root.right);
        List<Integer> re = new ArrayList<Integer>();
        re.add(root.val);
        for(int i=0;i<Math.max(left.size(), right.size());i++){
            if(i>=right.size())
                re.add(left.get(i));
            else
                re.add(right.get(i));
        }
        return re;
    }

  • 0
    R

    Nice solution! I just always get a little bit confused with the Divide and Conquer methods.. lol!


  • 0
    J

    Innovative. However, It seems to me that stack maintenance and obj construction/destruction incur extra overhead. Does this solution has any advantage over the level order + queue solution other than being innovative? Thanks!


  • 1
    M

    You are right. The ArrayList will be constructed and destructed repeatedly and recursion will cause stack cost. Not better than solutions maintaining just one List in performance.
    Neat codes and brief thought are the advantages of this solution I think. Suitable for phone interview.


  • 0
    H

    What is the time complexity? I always find it hard to analyze the time complexity for divide and conquer method.


  • 0
    M

    I am not sure the worst case using this algorithm so it's a little hard to analyze with detail.
    But I think it will not be more than O(nlogn), similar to Merge Sort.


  • 2

    Worst case is O(n^2), so it's very slow. Think about a tree with only one node at every level.


  • 0
    M

    You are right. When the tree is highly unbalanced, the algorithm is not efficient. Thanks for pointing out.


  • 0

    Thanks for sharing, its always good to find some new way of doing things. Though, it might not be the most effective one :)


Log in to reply
 

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