66.Binary Tree Preorder Traversal

1.Description(Easy)

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

Example

Given:

    1
   / \
  2   3
 / \
4   5

return[1,2,4,5,3].

Challenge

Can you do it without recursion?

2.Code

Recurision: Divided Conquer && Traversal

Non-recursion:Stack

Divided Conquer:

 public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<Integer>();
        if(root==null){
            return result;
        }

        List<Integer> left=preorderTraversal(root.left);
        List<Integer> right=preorderTraversal(root.right);

        result.add(root.val);
        result.addAll(left);
        result.addAll(right);

        return result;
    }

Traversal:

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<Integer>();
        Helper(result,root);
        return result;
    }

    public void Helper(List<Integer> result,TreeNode root){
        if(root==null){
            return;
        }
        result.add(root.val);
        Helper(result,root.left);
        Helper(result,root.right);
    }

Non-recursive:

由于stack的特性，先压root, 再压root.right,再压root.left

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<Integer>();
        Stack<TreeNode> stack=new Stack<TreeNode>();

        if(root==null){
            return result;
        }

        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode current=stack.pop();
            result.add(current.val);
            if(current.right!=null){
                stack.push(current.right);
            }
            if(current.left!=null){
                stack.push(current.left);
            }
        }
        return result;
    }