题目:
解答:
递归求解。
基本情况:先序与中序数组长度小于1时,返回NULL。
递归步骤:首先去欸的那个preorder的第一个元素一定是该树的root,再在inorder中找到该元素,标记为index,index左部分为左子树的中序,右部分为右子树的中序;随后,通过左右子树中序的长度(可能为0),在preorder中确定左右子树的先序。
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 13 TreeNode *buildTreeHelper(vector<int>& preorder, int ps, int pe, vector<int>& inorder, int is, int ie) 14 { 15 if ((pe - ps < 0) || (pe - ps) != (ie - is)) 16 { 17 return NULL; 18 } 19 20 TreeNode *root = new TreeNode(preorder[ps]); 21 22 int index = -1; 23 for (int i = is; i <= ie; i++) 24 { 25 if (inorder[i] == root->val) 26 { 27 index = i; 28 break; 29 } 30 } 31 32 if (index == -1) 33 { 34 return root; 35 } 36 37 int leftprelen = index - is; 38 root->left = buildTreeHelper(preorder, ps + 1, ps + leftprelen, inorder, is, index - 1); 39 root-> right = buildTreeHelper(preorder, ps + leftprelen + 1, pe, inorder, index + 1, ie); 40 41 return root; 42 } 43 44 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 45 { 46 return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1); 47 } 48 };
原文:https://www.cnblogs.com/ocpc/p/12817672.html