中序遍历序列与前序遍历序列构造二叉树

/** * 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) { int sz = preorder.size(); return build(preorder, 0, sz - 1, inorder, 0, sz - 1); } TreeNode* build(vector<int>& preorder, int prestart, int preend, vector<int>& inorder, int instart, int inend){ //这一步很关键,因为前序序列是靠中序序列pivol两侧的长度来截取,在递归中迟早会使头超过尾 if(prestart > preend) return NULL; int sz = preorder.size(); int rootVal = preorder[prestart]; int pivol; for(int i=0;i<sz;i++){ if(inorder[i]==rootVal){ pivol = i; break; } } int leftsz = pivol - instart; TreeNode* root = new TreeNode(rootVal); root->left = build(preorder, prestart + 1, prestart + leftsz, inorder, instart, pivol - 1); root->right = build(preorder, prestart + leftsz + 1, preend, inorder, pivol + 1, inend); return root; } };

后序遍历序列的不同在于，取的是序列的最后一位。

/** * 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>& inorder, vector<int>& postorder) { int sz = inorder.size(); return build(inorder, 0, sz - 1, postorder, 0, sz - 1); } TreeNode* build(vector<int>& inorder, int inStart, int inEnd, vector<int>& postorder, int postStart, int postEnd){ if(postStart > postEnd) return NULL; int sz = inorder.size(); int rootVal = postorder[postEnd]; int pivol; for(int i=0;i<sz;i++){ if(inorder[i]==rootVal){ pivol = i; break; } } int leftsz = pivol - inStart; TreeNode* root = new TreeNode(rootVal); root->left = build(inorder, inStart, pivol - 1, postorder, postStart, postStart + leftsz - 1); root->right = build(inorder, pivol + 1, inEnd, postorder, postStart + leftsz, postEnd - 1); return root; } };