Given preorder and inorder traversal of a tree, construct the binary tree.
Note:You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]Return the following binary tree:
3 / \ 9 20 / \ 15 7-----------------------------------------------------------------------------------就是从先序遍历和中序遍历构建踹个二叉树，可以用递归方式，注意递归的终止条件。和 leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal几乎一样。 参考博客：http://www.cnblogs.com/grandyang/p/4296500.html C++代码： /** * 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 build(preorder,0,preorder.size() - 1,inorder,0,inorder.size() - 1); } TreeNode* build(vector<int> &preorder,int pleft,int pright,vector<int> &inorder,int ileft,int iright){ if(pleft > pright || ileft > iright) return NULL; //递归的终止条件。 int i = 0; TreeNode *cur = new TreeNode(preorder[pleft]); for(i = ileft; i < inorder.size(); i++){ if(inorder[i] == cur->val) break; } cur->left = build(preorder,pleft + 1,pleft + i - ileft,inorder,ileft,i-1); cur->right = build(preorder,pleft + i - ileft + 1,pright,inorder,i+1,iright); return cur; } };也有一个方法：
/** * 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 build(preorder,inorder); } TreeNode* build(vector<int> &preorder,vector<int> &inorder){ if(preorder.size() == 0 || inorder.size() == 0) return NULL; //递归条件。当然，也还可以加上if(preorder.size() == 1 || inorder.size() == 1) return cur;这个递归条件。 int rootval = preorder[0]; int i = 0; for(i = 0; i < inorder.size(); i++){ if(inorder[i] == rootval) break; } vector<int> inleft,inright,preleft,preright; for(int k = 1; k < i + 1; k++) preleft.push_back(preorder[k]); for(int k = i + 1; k < preorder.size(); k++){ preright.push_back(preorder[k]); inright.push_back(inorder[k]); } for(int k = 0; k < i; k++) inleft.push_back(inorder[k]); TreeNode *cur = new TreeNode(rootval); cur->left = build(preleft,inleft); cur->right = build(preright,inright); return cur; } };这两个方法从思想上是一样的，只不过代码的实现有所不同。
转载于:https://www.cnblogs.com/Weixu-Liu/p/10772366.html
