LeetCode-106. Construct Binary Tree from Inorder and Postorder Traversal

LeetCode-106. 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

inorder = [9,3,15,20,7]postorder = [9,15,7,20,3]

Return the following binary tree:

3 / \ 9 20 / \ 15 7

题解：

同105

class Solution {public: TreeNode* buildTree(int pleft, int pright, int ileft, int iright, vector &postorder, vector &inorder) { if (pleft > pright || ileft > iright) { return NULL; } TreeNode *root = new TreeNode(postorder[pright]); int k = 0; for (int i = ileft; i <= iright; i++) { if (inorder[i] == postorder[pright]) { k = i; break; } } int llen = k - ileft; int rlen = iright - k; root->left = buildTree(pright - rlen - llen - 1, pright - rlen - 1, ileft, k - 1, postorder, inorder); root->right = buildTree(pright - llen - 1, pright - 1, k + 1, iright, postorder, inorder); return root; } TreeNode* buildTree(vector& inorder, vector& postorder) { int n = inorder.size(); if (n == 0) { return 0; } TreeNode *root = buildTree(0, n - 1, 0, n - 1, postorder, inorder); return root; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。