LeetCode-105. Construct Binary Tree from Preorder and Inorder Traversal

LeetCode-105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

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

Return the following binary tree:

3 / \ 9 20 / \ 15 7

题解：

通过四个指针获取左右子树的起点和终点位置。

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

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