O(n) reverse inorder traversal solution with O(1) space


  • 0
    S
    public class Solution {
    int level =0;
    public List<Integer> rightSideView(TreeNode root) {
       List<Integer> list = new ArrayList();
       if(root == null)
            return list;
        reverseInorderTraversal(root, list, level+1);
        return list;
    }
    public void reverseInorderTraversal(TreeNode root, List<Integer> list, int lev)
    {
        if(root == null)
            return;
        if(lev > level)
        {
            list.add(root.val);
            level = lev;
        }
        reverseInorderTraversal(root.right, list, lev+1);
        reverseInorderTraversal(root.left, list, lev+1);
    }
    }

Log in to reply
 

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