首页 > 代码库 > 【LeetCode】Construct Binary Tree from Inorder and Postorder Traversal
【LeetCode】Construct Binary Tree from Inorder and Postorder Traversal
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.
根据定义，后序遍历postorder的最后一个元素为根。
由于元素不重复，通过根可以讲中序遍历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> &inorder, vector<int> &postorder) { return Helper(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1); } TreeNode *Helper(vector<int> &inorder, int begin1, int end1, vector<int> &postorder, int begin2, int end2) { if(begin1 > end1) return NULL; else if(begin1 == end1) return new TreeNode(inorder[begin1]); else { //in posterorder, root is the last visitor TreeNode* root = new TreeNode(postorder[end2]); int ind; for(ind = begin1; ind <= end1; ind ++) { if(inorder[ind] == postorder[end2]) break; } //inorder[ind] is the root value in inorder //left has ind-begin1 nodes root->left = Helper(inorder, begin1, ind-1, postorder, begin2, begin2+ind-begin1-1); //right has end1-ind nodes root->right = Helper(inorder, ind+1, end1, postorder, end2-end1+ind, end2-1); return root; } }};
【LeetCode】Construct Binary Tree from Inorder and Postorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。