来源：力扣 （LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意：你可以假设树中没有重复的元素。
例如，给出前序遍历 preorder = [3,9,20,15,7]，中序遍历 inorder = [9,3,15,20,7]，返回如下的二叉树：
|
1 2 3 4 5 |
3 / \ 9 20 / \ 15 7 |
二、题解
这道题在 《剑指 offer 》也出现了，题目完全一样。主要用到了树的两个特性：
- 前序遍历的首元素为根节点。
- 中序遍历中，根节点的左边是左子树，根节点的右边是右子树。
解题的思路就是：通过前序遍历得到根节点，然后在中序遍历中找到这个节点，再通过递归的方式找出左右子树。
详细的分析可以参考 《剑指 offer 》面试题 7：重建二叉树。
三、代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
/** * 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) { size_t len = preorder.size(); if (len < 1) return nullptr; return buildTreeCore(preorder, 0, len - 1, inorder, 0, len - 1); } private: TreeNode *buildTreeCore(vector<int> &preOrder, unsigned int preStart, unsigned int preEnd, vector<int> &inOrder, unsigned int inStart, unsigned int inEnd) { unsigned int idx, lchild_len; TreeNode *root = nullptr; root = new TreeNode(preOrder[preStart]); if (preStart == preEnd) { return root; } // 在中序遍历中找到根节点 idx = inStart; while (idx < inEnd && root->val != inOrder[idx]) { idx++; } // 左子树的长度 lchild_len = idx - inStart; if (lchild_len > 0) { // 计算左子树 root->left = buildTreeCore(preOrder, preStart + 1, preStart + lchild_len, inOrder, inStart, idx - 1); } if (lchild_len < preEnd - preStart) { // 计算右子树 root->right = buildTreeCore(preOrder, preStart + lchild_len + 1, preEnd, inOrder, idx + 1, inEnd); } return root; } }; |
执行通过：
