105.Construct Binary Tree from Preorder and Inorder Traversal

Tags: Tree Medium

Link: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

---

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

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

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

---

Answer:

1. 前序的第一个为根，在中序中找到根的位置。
2. 中序中根的左右两边即为左右子树的中序遍历。同时可知左子树的大小size-left。
3. 前序中根接下来的size-left个是左子树的前序遍历。
4. 由此可以递归处理左右子树。

/**
 * 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 {
public:
    using Iter = vector<int>::iterator; 
    //C++11新标准写法，也可以写成typedef vector<int>::iterator Iter;
    TreeNode *buildTreeFromPreAndIn(Iter in_start, Iter in_end, Iter pre_start, Iter pre_end){
        if(pre_start == pre_end) return nullptr;
        if(in_start == in_end) return nullptr;

        auto root = new TreeNode(*pre_start); //建立根节点

        auto inRootPos = find(in_start, in_end, *pre_start); //在中序遍历中找到pre_start来划分左右子树
        auto leftSize = distance(in_start, inRootPos); //前序遍历中左子树的大小

        root -> left = buildTreeFromPreAndIn(in_start, inRootPos, pre_start + 1, pre_start + 1 + leftSize);
        root -> right = buildTreeFromPreAndIn(inRootPos + 1, in_end, pre_start + 1 + leftSize, pre_end);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTreeFromPreAndIn(inorder.begin(), inorder.end(), preorder.begin(), preorder.end());
    }
};

不使用迭代器的解法：

/**
 * 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 {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = preorder.size(), n = inorder.size();
        return build(0, m, 0, n, preorder, inorder);
    }

    TreeNode *build(int pre_start, int pre_end, int in_start, int in_end, vector<int>& preorder, vector<int>& inorder)
    {
        if (pre_start == pre_end || in_start == in_end) return NULL;

        TreeNode *root = new TreeNode(preorder[pre_start]);
        int pos = in_start;
        for (int i = in_start; i < in_end; ++i) {
            if (inorder[i] == preorder[pre_start]) {
                pos = i; break;
            }
        }
        int leftSize = pos - in_start;

        root -> left = build(pre_start + 1, pre_start + 1 + leftSize, in_start, pos, preorder, inorder);
        root -> right = build(pre_start + 1 + leftSize, pre_end, pos + 1, in_end, preorder, inorder);
        return root;
    }
};

类似的题目是：一本通-1339：【例3-4】求后序遍历，好处是锻炼手动建树的能力。