algorithm - 给定二叉树的有序遍历和无序遍历，无需递归

给定一棵树的按序和按序遍历，如何以非递归方式重新构造树。
例如：
重新构建以下树

                     1
       2                             3
 4           5                6             7
                  8                     9

鉴于
顺序遍历：4，2，5，8，1，6，3，9，7
前序遍历：1，2，4，5，8，3，6，7，9
注意：有很多对递归实现的引用。例如，可以引用Construct Tree from given Inorder and Preorder traversals不过，这里的目的是寻找非递归实现。

最佳答案

这样做的目的是防止树节点在堆栈中按序遍历，直到在按序遍历中找不到对应的节点为止。找到对应项后，必须已经访问了节点左子树中的所有子节点。
下面是非递归Java实现。

public TreeNode constructTree(int[] preOrder, int[] inOrder) {

    if (preOrder.length == 0) {
      return null;
    }

    int preOrderIndex = 0;
    int inOrderIndex = 0;

    ArrayDeque<TreeNode> stack = new ArrayDeque<>();

    TreeNode root = new TreeNode(preOrder[0]);
    stack.addFirst(root);
    preOrderIndex++;

    while (!stack.isEmpty()) {

      TreeNode top = stack.peekFirst();

      if (top.val == inOrder[inOrderIndex]) {

        stack.pollFirst();
        inOrderIndex++;

        // if all the elements in inOrder have been visted, we are done
        if (inOrderIndex == inOrder.length) {
          break;
        }

        // Check if there are still some unvisited nodes in the left
        // sub-tree of the top node in the stack
        if (!stack.isEmpty()
            && stack.peekFirst().val == inOrder[inOrderIndex]) {
          continue;
        }

        // As top node in stack, still has not encontered its counterpart
        // in inOrder, so next element in preOrder must be right child of
        // the removed node
        TreeNode node = new TreeNode(preOrder[preOrderIndex]);
        preOrderIndex++;
        top.right = node;
        stack.addFirst(node);

      } else {
        // Top node in the stack has not encountered its counterpart
        // in inOrder, so next element in preOrder must be left child
        // of this node
        TreeNode node = new TreeNode(preOrder[preOrderIndex]);
        preOrderIndex++;
        top.left = node;
        stack.addFirst(node);
      }
    }

    return root;
  }

关于algorithm - 给定二叉树的有序遍历和无序遍历，无需递归，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48352513/