[Java] Easy to understand solution explanation below


  • 0

    The idea is that we want to find the rightSideView of the left subtree and right subtree.

    Let L = rightSideView of left subtree, R = same thing for right subtree, Ln = length of rightSideView of left subtree and Rn = same thing for right subtree. The key observation is that we want to ignore the first Rn elements of L because they will be "covered" by the elements of R. So in our output we essentially construct a list that looks like:

    res = [R[0], ..., R[Rn - 1], Ln[Rn], ..., Ln[Ln - 1]]

    ** Another key point is that if Ln < Rn, then L will not contribute anything to the final result **

    public List<Integer> rightSideView(TreeNode root) {
            // base
            List<Integer> res = new ArrayList<Integer>();
            if(root == null) return res;
            
            res.add(root.val);
            
            List<Integer> rt = rightSideView(root.right);
            List<Integer> lft = rightSideView(root.left);
            lft = lft.size() > rt.size() ? lft.subList(rt.size(), lft.size()) : new ArrayList<Integer>();
            res.addAll(rt);
            res.addAll(lft);
                
            return res;
        }
    

Log in to reply
 

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