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. For example, given 1 2 inorder = [9,3,15,20,7] postorder = [9,15,7,20,3] Return the following binary tree: 1 2 3 4 5 3 / \ 9 20 / \ 15 7 实现： 递归方式，根据二叉树中序遍历和后续遍历，创建二叉树。中序遍历： 左-根-右， 后续遍历： 左-右-根， 所以可以通过后续遍历的最后一个节点找到根节点，并生成根节点， 因为二叉树没有重复节点， 就 可以在中序遍历数据中找到根节点，再分成左右两个子树，递归执行下去，遍历完所有节点。 通过postorder获取根节点， 通过inorder生成左右子树，查找节点在中序遍历数据组里位置，可以通过unordered_map实现。 不使用map情况下 时间复杂度 O(N^2) , 使用map查找O(N) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { unordered_map <int, int> treemap; for (int i=0; i<inorder.size();i++) { treemap[inorder[i]] = i; } int index = inorder.size()-1; return helper(inorder, postorder, 0, inorder.size()-1, &index, treemap); } TreeNode *helper(vector<int> & inorder, vector<int>& postorder, int left, int right, int *index , unordered_map<int, int>&treemap){ //check if (left > right){ return NULL; } // create root node /* destory postorder vector int val = postorder.back(); TreeNode *node = new TreeNode(val); postorder.pop_back(); */ int val = postorder[*index]; TreeNode *node = new TreeNode(val); (*index)--; // search inorder by array /* int root = -1; for (int i=left ; i <=right; i ++){ if (val == inorder[i]){ root = i; break; } } if (root == -1){ return node; }*/ // search inorder by map int root = treemap[val]; // create left & right node node->right = helper(inorder, postorder, root+1, right, index, treemap); node->left = helper(inorder, postorder, left, root-1, index, treemap); return node; } };