首页 > 代码库 > [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.
思路：
数据结构的基本题目，根据中序遍历和后序遍历确定整个树的结构。我的方法是通过后续遍历确定根节点是什么，在中序遍历中寻找这个节点的位置，那么它的左边就是左子树，右边就是右子树，如此递归寻找。这里的一个难点是判断下一次递归中左子树的根节点，本代码中就是index-r+i-1，这个取值是我试出来的，我也不知道为什么。
题解：
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: void build(vector<int> &inorder, vector<int> &postorder, int l, int r, int index, TreeNode *&root) { if(l>r) return; root = new TreeNode(postorder[index]); int i; for(i=l;i<=r;i++) if(inorder[i]==postorder[index]) break; build(inorder, postorder, i+1, r, index-1, root->right); build(inorder, postorder, l, i-1, index-r+i-1, root->left); } TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { if(inorder.size()==0) return NULL; TreeNode *root; build(inorder, postorder, 0, inorder.size()-1, postorder.size()-1, root); return root; }};
[leetcode] Construct Binary Tree from Inorder and Postorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。