二叉树的先序遍历（非递归版）.md

####【题目】

按照二叉树的先序遍历打印二叉树，并且不能使用递归。

####【难度】

易

####解答

二叉树的先序遍历顺序是根-左-右。我们可以采用一个栈来辅助，我们把先序遍历的结果放到一个 ArrayList 容器中作为返回值，具体步骤如下：

1、把二叉树的根节点 root 放进栈。

2、如果栈不为空，从栈中取出一个节点，把该节点放入容器的尾部；如果该节点的右子树不为空，则把有节点放入栈；如果该节点的左子树不为空，则把左子树放入栈中。

3、一直重复步骤 2 ，直到栈为空，此时遍历结束，代码如下：

代码如下：

    // 迭代版
    static List<Integer> preOderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null)
            return result;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.pop();
            result.add(tmp.val);
            if(tmp.right != null)
                stack.push(tmp.right);
            if(tmp.left != null)
                stack.push(tmp.left);
        }
        return result;
    }

学习更多算法 + 计算机基础知识，欢迎关注我的微信公众号，每天准时推送技术干货