3 Different Solutions


  • 41

    Recursive method with List as returning value:

    	public List<Integer> preorderTraversal(TreeNode root) {
    		List<Integer> pre = new LinkedList<Integer>();
    		if(root==null) return pre;
    		pre.add(root.val);
    		pre.addAll(preorderTraversal(root.left));
    		pre.addAll(preorderTraversal(root.right));
    		return pre;
    	}
    

    Recursive method with Helper method to have a List as paramater, so we can modify the parameter and don't have to instantiate a new List at each recursive call:

    	public List<Integer> preorderTraversal(TreeNode root) {
    		List<Integer> pre = new LinkedList<Integer>();
    		preHelper(root,pre);
    		return pre;
    	}
    	public void preHelper(TreeNode root, List<Integer> pre) {
    		if(root==null) return;
    		pre.add(root.val);
    		preHelper(root.left,pre);
    		preHelper(root.right,pre);
    	}
    

    Iterative method with Stack:

    	public List<Integer> preorderIt(TreeNode root) {
    		List<Integer> pre = new LinkedList<Integer>();
    		if(root==null) return pre;
    		Stack<TreeNode> tovisit = new Stack<TreeNode>();
    		tovisit.push(root);
    		while(!tovisit.empty()) {
    			TreeNode visiting = tovisit.pop();
    			pre.add(visiting.val);
    			if(visiting.right!=null) tovisit.push(visiting.right);
    			if(visiting.left!=null) tovisit.push(visiting.left);
    		}
    		return pre;
    	}

Log in to reply
 

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