問題描述 Given PReorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
解決思路 利用遞歸建樹的思想，找到左右子樹的list，然后遞歸下去，就可以了。
代碼
/** * 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) { return helper(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1); } TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int pre_begin, int pre_end, int in_begin, int in_end) { if (pre_end < pre_begin) return NULL; TreeNode *root = new TreeNode(preorder[pre_begin]); int left_len = 0; for (int i = in_begin; i <=in_end; ++i) { if (inorder[i] == preorder[pre_begin]) break; ++left_len; } root->left = helper(preorder,inorder,pre_begin+1,pre_begin+left_len,in_begin,in_begin+left_len-1); root->right = helper(preorder,inorder,pre_begin+left_len+1,pre_end,in_begin+left_len+1,in_end); return root; }};新聞熱點
疑難解答
