leetcode 105题，由树的前序序列和中序序列构建树结构。详细解答参考《剑指offer》page56.
先序遍历结果的第一个节点为根节点，在中序遍历结果中找到根节点的位置。然后就可以将问题拆分，递归求解。
/** * 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 * buildTreeCore(vector<int>& preorder, vector<int>& inorder, int p1, int p2, int p3, int p4) { int rootValue = preorder[p1]; TreeNode * root = new TreeNode(rootValue); if (p1 == p2) { if (p3 == p4 && preorder[p1] == inorder[p3]) { return root; } } int pr = p3; while (pr <= p4 && inorder[pr] != rootValue) pr++; int leftLength = pr - p3; int p5 = p1 + leftLength; if (leftLength > 0) { root->left = buildTreeCore(preorder, inorder, p1 + 1, p5, p3, pr - 1); } if (leftLength < p2 - p1) { root->right = buildTreeCore(preorder, inorder, p5 + 1, p2, pr + 1, p4); } return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if (preorder.size() <= 0 || inorder.size() <= 0) { return NULL; } return buildTreeCore(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1); } };
转载于:https://www.cnblogs.com/vincent93/p/6686669.html
