For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively
java code ：recursive solution:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList preorderTraversal(TreeNode root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
ArrayList res = new ArrayList();
if(root == null)
return res;
pre(res,root);
return res;
}
public void pre(ArrayList res, TreeNode root)
{
res.add(root.val);
if(root.left != null)
pre(res, root.left);
if(root.right != null)
pre(res, root.right);
}
}
iteratively solution:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList preorderTraversal(TreeNode root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
ArrayList res = new ArrayList();
if(root == null)
return res;
Stack st = new Stack();
st.push(root);
while(!st.isEmpty())
{
TreeNode cur = st.peek();
res.add(cur.val);
st.pop();
if(cur.right != null)
st.push(cur.right);
if(cur.left != null)
st.push(cur.left);
}
st = null;
return res;
}
}