题目地址

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]

返回如下的二叉树：

3 / \ 9 20 / \ 15 7

解答

序遍历的顺序是 root -> left -> right，这就能方便的从根开始构造一棵树。

首先，preorder 中的第一个元素一定是树的根，这个根又将 inorder 序列分成了左右两棵子树。现在我们只需要将先序遍历的数组中删除根元素，然后重复上面的过程处理左右两棵子树。

代码：

/** * 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: int findPos( int target, vector<int>& inorder, int start, int end){ for( int i = start; i < end; i++) if( inorder[i] == target) return i; return -1; } TreeNode* build( vector<int>& preorder, int preBegin, vector<int>& inorder, int start, int end){ if( start == end) //边界条件 return NULL; TreeNode* now = new TreeNode( preorder[preBegin]); int pos = findPos( preorder[preBegin], inorder, start, end); if( pos == -1) return now; now->left = build( preorder, preBegin + 1, inorder, start, pos); now->right = build( preorder, preBegin + pos - start + 1, inorder, pos + 1, end); return now; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if( preorder.size() == 0) return NULL; return build( preorder, 0, inorder, 0, inorder.size()); } };