首页 > 代码库 > [LeetCode] Construct Binary Tree from Inorder and Postorder Traversal
[LeetCode] Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
方法：在inorder中寻找postorder的最后一个，然后左右递归，注意处理好各个low，high边界
1 class Solution 2 { 3 public: 4 TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) 5 { 6 return buildTree(postorder, 0, postorder.size()-1, 7 inorder, 0, inorder.size()-1); 8 } 9 10 TreeNode *buildTree(vector<int> &postorder, int low1, int high1,11 vector<int> &inorder, int low2, int high2)12 {13 //cout << "==============" <<endl;14 //cout << "low1 = \t" << low1 <<endl;15 //cout << "high1= \t" << high1 <<endl;16 //cout << "low2 = \t" << low2 <<endl;17 //cout << "high2= \t" << high2 <<endl;18 if(low1 > high1 || low2> high2)19 return NULL;20 21 TreeNode * p = new TreeNode(postorder[high1]);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] == postorder[high1])30 break;31 } 32 //cout << "index= \t" << index<<endl;33 34 if(index != low2)35 p->left = buildTree(postorder, low1,(low1) + (index-1-low2), inorder, low2, index-1);36 if(index != high2)37 p->right = buildTree(postorder, (high1-1) - (high2-index-1) ,high1-1, inorder, index+1, high2);38 39 return p;40 }41 } ;
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。