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

题目链接：

---

思路分析

给一个二叉树的前序和中序遍历的结果，构建出这棵二叉树。

使用递归的方式解题。根据前序遍历和中序遍历的性质，前序遍历先访问根结点，而中序遍历先访问左子树，所以前序遍历的第一个元素在中序遍历中的位置可以将中序遍历分为左右两子树。根据这个特点，每次递归找到此时前序的第一个元素，然后找到对应中序遍历中的位置，再次递归就行，递归的结束条件是前序遍历的开始与结束位置重合。

每次分割后的左右子树的范围为： 左子树： preorder：[pstart + 1 – pstart + root - istart] inorder: [istart – root - 1] 右子树： preorder: [pstart + root - istart + 1 – pend]活着 [pend - iend + root + 1] //pend - (iend - root) + 1，不太直观。root - istart 就是左子树的元素个数，再加一就是右子树的根结点了。 inorder:[root+1 – iend]

代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return builder(preorder, 0, preorder.size() - 1,inorder, 0, inorder.size() - 1); } TreeNode* builder(vector<int>& preorder, int pstart, int pend, vector<int>& inorder, int istart, int iend){ if (pstart > pend) return NULL; TreeNode* node = new TreeNode(preorder[pstart]); int root; for (int i = istart; i <= iend; i++){ if (inorder[i] == preorder[pstart]){ root = i; break; } } node->left = builder(preorder, pstart + 1, pstart + root - istart ,inorder, istart, root - 1); node->right = builder(preorder, pstart + root - istart + 1, pend, inorder, root + 1, iend); return node; } };

时间复杂度： O(未知) O ( 未 知 ) 空间复杂度： O(未知) O ( 未 知 )

---

反思

再次回看一脸懵逼。