根據一棵樹的前序遍歷與中序遍歷構造二叉樹。

注意:
你可以假設樹中沒有重復的元素。

例如，給出

前序遍歷 preorder =?[3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：

? ? 3
? ?/ \
? 9 ?20
? ? / ?\
? ?15 ? 7

?

思路：現在前序遍歷中找到第一個數，根據這個數去中序二叉樹查找到相應位置，然后根據這個位置就可以得到當前節點的左子樹的初始位置和終止位置，并且根據長度直到在前序列表中對應的左子樹起始和終止位置，那么遞歸尋找左子樹根節點即可，右子樹同理。

/*** 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) {if(preorder.empty() || inorder.empty())return NULL;int pre_start = 0; int pre_end = preorder.size()-1;int in_start = 0; int in_end = inorder.size()-1;return core(preorder, inorder, pre_start, pre_end, in_start, in_end);}TreeNode* core(vector<int>& preorder, vector<int>& inorder, int pre_start, int pre_end, int in_start, int in_end){int rootval = preorder[pre_start];TreeNode* root = new TreeNode(rootval);if(pre_start == pre_end){if((in_start == in_end) && (preorder[pre_start] == inorder[in_end]))return root;elsereturn NULL;}int in_left_end = -1;for(int i=in_start;i<=in_end;++i){if(inorder[i]==rootval){in_left_end = i;}}if(in_left_end==-1)return NULL;if(in_left_end-in_start>0)root->left = core(preorder, inorder, pre_start+1, pre_start+in_left_end-in_start, in_start, in_left_end-1);if(pre_end-(pre_start+in_left_end-in_start)>0)root->right = core(preorder, inorder, pre_start+in_left_end-in_start+1, pre_end, in_left_end+1, in_end);return root;} };

?

總結

以上是生活随笔為你收集整理的从前序与中序遍历序列构造二叉树—leetcode105的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。