构造二叉树给定其中序和前序遍历而不递归

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

注意：有很多递归实现的参考。例如，可以参考 Construct Tree from given Inorder and Preorder traversals。然而这里的目的是找到非递归实现。

Answer 1

想法是在 preorder 遍历中将树节点保留在堆栈中，直到在 inorder 遍历中找不到它们的对应物。一旦找到对应节点，则该节点的左子树中的所有子节点都必须已经被访问过。

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

构造二叉树给定其中序和前序遍历而不递归

Construct binary tree given its inorder and preorder traversals without recursion

iteration

algorithm

tree

recursion

binary-tree