144. Binary Tree Preorder Traversal java solutions

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

For example:
Given binary tree {1,#,2,3},

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Subscribe to see which companies asked this question

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public List<Integer> preorderTraversal(TreeNode root) {
12         ArrayList<Integer> anslist = new ArrayList<Integer>();
13         if(root == null) return anslist;
14         Stack<TreeNode> s = new Stack<TreeNode>();
15         s.push(root);
16         while(!s.empty()){
17             TreeNode n = s.pop();
18             anslist.add(n.val);
19             if(n.right != null) s.push(n.right);
20             if(n.left != null) s.push(n.left);
21         }
22         return anslist;
23     }
24 }

使用栈来模拟先序遍历。递归的方法很简单，这里就不写了。