For problem 10.11 (where the book solution is recursive), I found that we can iteratively read the preorder traversal from right to left and reconstruct the tree by using a stack. I just want to share my algorithm here.
If we get a nullptr from the preorder, we push to stack. Otherwise, make a new node with the top of the stack as the left child and the below-the-top of the stack as the right child, then push the new node to the stack. Finally, the stack will contain the root of the tree.
Time: O(n), space: O(height of tree)
typedef BinaryTreeNode<int> NodeType;
typedef unique_ptr<NodeType> NodePtr;
NodePtr ReconstructBinaryTree(const vector<int*>& preorder) {
stack<NodePtr> traversal_stack;
for (int i = preorder.size(); i >= 0; --i) {
int* cur = preorder[i];
if (cur == nullptr) {
traversal_stack.emplace(nullptr);
} else {
auto left_node = move(traversal_stack.top());
traversal_stack.pop();
auto right_node = move(traversal_stack.top());
traversal_stack.pop();
auto new_node = NodePtr(new NodeType{*cur, move(left_node), move(right_node)});
}
}
return move(traversal_stack.top());
}