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

xiaoxiao2021-02-28  6

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:你可以假设树中没有重复的元素。

例如,给出

前序遍历 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.size()) return NULL; int middle = preorder[0]; vector<int> preleft; vector<int> preright; vector<int> inleft; vector<int> inright; int i, j; i = 0; j = 1; for(;i < inorder.size();i++){ if(inorder[i] != middle) inleft.push_back(inorder[i]); else break; } i++; for(;i < inorder.size();i++){ inright.push_back(inorder[i]); } for(;j <= inleft.size();j++){ preleft.push_back(preorder[j]); } for(;j < preorder.size();j++){ preright.push_back(preorder[j]); } TreeNode* T = new TreeNode(middle); T->left = buildTree(preleft, inleft); T->right = buildTree(preright, inright); return T; } };
转载请注明原文地址: https://www.6miu.com/read-2350241.html

最新回复(0)