3 binary-tree-preorder-traversal

题目描述

求给定的二叉树的前序遍历。
例如：
给定的二叉树为{1,#,2,3},
1↵ ↵ 2↵ /↵ 3↵
返回：[1,2,3].
备注；用递归来解这道题太没有新意了，可以给出迭代的解法么？

代码

思想
前序遍历的非递归

public ArrayList<Integer> preorderTraversal (TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(root==null)return list;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(root!=null||!stack.isEmpty()) {
            while(root!=null) {
                stack.push(root);
                list.add(root.val);
                root = root.left;
            }
            if(!stack.isEmpty()) {
                root = stack.pop();
                root = root.right;
            }
        }         
        return list;        
    }