Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

Given binary tree {1,#,2,3},
Screen Shot 2016-04-04 at 10.59.11 AM.png
return [1,2,3].

Solution 1: recursive method

//preorder: ROOT, L, R
//inorder: L, ROOT, R
//postorder:L, R, ROOT
public class Solution {
    public List<Integer> result = new ArrayList<Integer> ();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return result;
        }
        result.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return result;
    }
}

 

Solution 2: stack method

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> returnList = new ArrayList<Integer>(); 
        
        if (root == null) {
            return returnList; 
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        
        while (!stack.empty()) {
            TreeNode n = stack.pop(); 
            returnList.add(n.val); 
            
            if (n.right != null) {
                stack.push(n.right);
            }
            
            if (n.left != null) {
                stack.push(n.left); 
            }
        }
        
        return returnList; 
    }
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s