首页 > 代码库 > [LeetCode] Construct Binary Tree from Preorder and Inorder Traversal
[LeetCode] 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.
方法一：最先想到的就是递归，注意low、high的计算，还有初始时NULL情况的处理。。
从inorder中寻找pre的第一个，然后左右递归
1 class Solution 2 { 3 public: 4 TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) 5 { 6 if(preorder.size() == 0 || inorder.size() == 0) 7 return NULL; 8 return buildTree(preorder, 0, preorder.size()-1, 9 inorder, 0, inorder.size()-1);10 } 11 12 TreeNode *buildTree(vector<int> &preorder, int low1, int high1,13 vector<int> &inorder, int low2, int high2)14 { 15 //cout << "==============" <<endl;16 //cout << "low1 = \t" << low1 <<endl;17 //cout << "high1= \t" << high1 <<endl;18 //cout << "low2 = \t" << low2 <<endl;19 //cout << "high2= \t" << high2 <<endl;20 21 TreeNode * p = new TreeNode(preorder[low1]);22 if(low1 == high1)23 { 24 return p;25 } 26 int index = 0;27 for(index = low2; index < high2; index++)28 { 29 if(inorder[index] == preorder[low1])30 break;31 }32 //cout << "index= \t" << index<<endl;33 34 if(index != low2)35 p->left = buildTree(preorder, low1+1,(low1+1) + (index-1-low2), inorder, low2, index-1);36 if(index != high2)37 p->right = buildTree(preorder, high1 - (high2-index-1) ,high1, inorder, index+1, high2);38 39 return p;40 }41 } ;
方法二：迭代
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。