还不快抢沙发

添加新评论

从前序与中序遍历序列构造二叉树。 例如,给出: ``` 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] ``` 返回的二叉树: ``` 3 / \ 9 20 / \ 15 7 ``` 解题思路: 无论是前序还是中序遍历,左子节点必然相等,前序的第一个元素为根节点,中序的第一个元素为最左侧的。若左边一个有n个元素,则根节点的为m,左树m+1,右树m+n+1。 ``` typedef vector::iterator Iter; TreeNode *buildTreeRecur(Iter istart, Iter iend, Iter pstart, Iter pend) { if (istart == iend)return NULL; int rootval = *pstart; Iter iterroot = find(istart, iend, rootval); TreeNode *res = new TreeNode(rootval); res->left = buildTreeRecur(istart, iterroot, pstart + 1, pend); res->right = buildTreeRecur(iterroot + 1, iend, pstart + 1 + (iterroot - istart), pend); return res; } TreeNode *buildTree(vector &preorder, vector &inorder) { return buildTreeRecur(inorder.begin(), inorder.end(), preorder.begin(), preorder.end()); } ```