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

Question

给定一棵树的有序和有序遍历，如何以非递归方式重构该树。

例如：

重建下面的树

                     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

注意：有很多关于递归实现的参考。例如，可以从给定的有序遍历和预序遍历引用构造树。但是，这里的目的是要找到非递归实现。

Answer 1

想法是保持树节点从堆栈序遍历，直到他们的对手中找不到序遍历。找到对应对象后，必须已访问该节点左子树中的所有子级。

以下是非递归 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;
  }