首页 > 代码库 > 【LeetCode】Construct Binary Tree from Preorder and Inorder Traversal
【LeetCode】Construct Binary Tree from Preorder and Inorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
可与Construct Binary Tree from Inorder and Postorder Traversal对照来看。
前序遍历Preorder的第一个节点为根，由于没有重复值，可使用根将中序Inorder划分为左右子树。
递归下去即可。
/** * Definition for binary tree * 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, 0, preorder.size()-1, inorder, 0, inorder.size()-1); } TreeNode *Helper(vector<int> &preorder, int begin1, int end1, vector<int> &inorder, int begin2, int end2) { if(begin1 > end1) return NULL; else if(begin1 == end1) return new TreeNode(preorder[begin1]); else { //preorder[begin1] is the root TreeNode* root = new TreeNode(preorder[begin1]); int ind; for(ind = begin2; ind <= end2; ind ++) { if(inorder[ind] == preorder[begin1]) break; } //left root->left = Helper(preorder, begin1+1, ind-begin2+begin1, inorder, begin2, ind-1); //right root->right = Helper(preorder, end1-end2+ind+1, end1, inorder, ind+1, end2); return root; } }};
【LeetCode】Construct Binary Tree from Preorder and Inorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。