Java Solution: pre-allocate space by height of tree


  • 0
    public class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> res = new LinkedList<>();
            if(root==null) return res;
    
           // allocate space each depth
            int[] path = new int[height(root)];
            dfs(root, 0, path);
            for(int n: path){
                res.add(n);
            }
            return res;
        }
        
        public void dfs(TreeNode root, int level, int[] path){
            path[level]=root.val;
            if(root.left!=null)
                dfs(root.left,level+1,path);
            
            // the rightmost node on this level will overwrite other nodes
            if(root.right!=null)
                dfs(root.right,level+1,path);
        }
        
        public int height(TreeNode root){
            if(root==null)
                return 0;
            return Math.max(height(root.left), height(root.right))+1;
        }
        
        
    }

Log in to reply
 

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