【二叉树打卡3】二叉树的先序遍历（非递归版）

帅地

发布于 2019-06-06 15:34:09

4180

发布于 2019-06-06 15:34:09

文章被收录于专栏：苦逼的码农苦逼的码农

前言

昨天把二叉树的先序遍历和中序遍历的题目给弄错了，今天重新补发下。

【题目】

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

【难度】

易

解答

二叉树的先序遍历顺序是根-左-右。我们可以采用一个栈来辅助，我们把先序遍历的结果放到一个 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.right);
        }
        return result;
    }

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-04-04，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法