105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution 1: recursion 19ms

这道题要求用先序和中序遍历来建立二叉树，跟之前那道Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树原理基本相同，针对这道题，由于先序的顺序的第一个肯定是根，所以原二叉树的根节点可以知道，题目中给了一个很关键的条件就是树中没有相同元素，有了这个条件我们就可以在中序遍历中也定位出根节点的位置，并以根节点的位置将中序遍历拆分为左右两个部分，分别对其递归调用原函数。代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode* build(vector<int>& preorder, int pleft, int pright, vector<int>& inorder, int ileft, int iright) {
        if (pleft > pright || ileft > iright) return NULL;

        // find root node
        int i = 0;
        for (i = ileft; i <= iright; ++i) {
            if (preorder[pleft] == inorder[i]) break;
        }

        TreeNode* cur = new TreeNode(preorder[pleft]);
        cur->left = build(preorder, pleft+1, pleft+i-ileft, inorder, ileft, i-1);
        cur->right = build(preorder, pleft+i-ileft+1, pright, inorder, i+1, iright);
        return cur;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
};

我们下面来看一个例子, 某一二叉树的中序和后序遍历分别为：

Preorder:　  　5　　4　　11　　8　　13　　9

Inorder:　　 　11　　4　　5　　13　　8　　9


5　　4　　11　　8　　13　　9　　　　　　=>　　　　　　　　 5

11　　4　　5　　13　　8　　9　　　　　　　　　　　　　　　/　　\



4　　11　　 　　8　　 13　　9　　　　　　=>　　　　　　　　5

11　　4　　　　 13　　8　　9　　 　　　　　　　　　　　  /　　\

　　　　　　　　　　　　　　　　　　　　　　　　　　　　  4　　　8



11　　　　 　　13　　　　9　　　　　　　　=>　　　　　　 5

11　　　　　　 13　　　　9　　　　 　　　　　　　　   /　　\

　　　　　　　　　　　　　　　　　　　　　　　　　　　　4　　　8

　　　　　　　　　　　　　　　　　　　　　　　　　　　/　　　 /     \

　　　　　　　　　　　　　　　　　　　　　　　　　　　11　　  13　　  9

做完这道题后，大多人可能会有个疑问，怎么没有由先序和后序遍历建立二叉树呢，这是因为先序和后序遍历不能唯一的确定一个二叉树，比如下面五棵树：

    1　　　　　　preorder:    1　　2　　3
   / \　　　　  inorder:     2　　1　　3
 2    3　　  　 postorder:　 2　　3　　1



       1   　　　　preorder:　　   1　　2　　3
      / 　　　　　 inorder:　　     3　　2　　1
    2 　　　　     postorder: 　　3　　2　　1
   /
 3



       1　　　　    preorder:　　  1　　2　　3
      / 　　　　　  inorder:　　    2　　3　　1
    2 　　　　　　postorder:　　3　　2　　1
      \
       3



       1　　　　     preorder:　　  1　　2　　3
         \ 　　　　   inorder:　　  1　　3　　2
          2 　　　　 postorder:　　3　　2　　1
         /
       3



       1　　　　     preorder:　　  1　　2　　3
         \ 　　　　　inorder:　　    1　　2　　3
          2 　　　　 postorder:　　3　　2　　1
            \
　　　　      3

从上面我们可以看出，对于先序遍历都为1 2 3的五棵二叉树，它们的中序遍历都不相同，而它们的后序遍历却有相同的，所以只有和中序遍历一起才能唯一的确定一棵二叉树。

Solution 2: iteration 19ms

I din't find iterative solutions discussed in the old Discuss. So, I thought, I will add my solution in here.

The idea is as follows:

1. Keep pushing the nodes from the preorder into a stack (and keep making the tree by adding nodes to the left of the previous node) until the top of the stack matches the inorder.

2. At this point, pop the top of the stack until the top does not equal inorder (keep a flag to note that you have made a pop).

3. Repeat 1 and 2 until preorder is empty. The key point is that whenever the flag is set, insert a node to the right and reset the flag.

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) return NULL;

        TreeNode* root = new TreeNode(preorder[0]);
        stack<TreeNode*> s; s.push(root);
        int idx = 0;

        for (int i = 1; i < preorder.size(); ++i) {
            TreeNode* cur = s.top();
            if (cur->val != inorder[idx]) {
                cur->left = new TreeNode(preorder[i]);
                s.push(cur->left);
            } else {
                while (!s.empty() && s.top()->val == inorder[idx]) {
                    cur = s.top(); s.pop(); ++idx;
                }

                if (idx < inorder.size()) {
                    cur->right = new TreeNode(preorder[i]);
                    s.push(cur->right);
                }
            }
        }
        return root;
    }
};