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

帅地

发布于 2019-06-06 15:33:50

3980

发布于 2019-06-06 15:33:50

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

【题目】

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

【难度】

易

解答

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

1、进入 while 循环，接着把根节点及其所有左子节点放入栈中。

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

3、一直重复步骤 2 ，直到栈为空并且当前节点也为空则退出循环。

可能看解释反而有点乱，直接看代码吧，配合代码就容易懂了。

代码如下：

   // 中序遍历
    public List<Integer> inOderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }

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

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

二叉树