Construct Binary Tree from Preorder and Inorder Traversal

最后更新于:2022-04-01 22:57:42

**一. 题目描述** Given preorder and inorder traversal of a tree, construct the binary tree.  Note: You may assume that duplicates do not exist in the tree. **二. 题目分析** 这道题考察了先序和中序遍历,先序是先访问根节点,然后访问左子树,最后访问右子树;中序遍历是先遍历左子树,然后访问根节点,最后访问右子树。 做法都是先根据先序遍历的概念,找到先序遍历的第一个值,即为根节点的值,然后根据根节点将中序遍历的结果分成左子树和右子树,然后就可以递归的实现了。 按照上述做法,时间复杂度为`O(n^2)`,空间复杂度为`O(1)` **三. 示例代码** ~~~ #include #include #include using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { private: TreeNode* buildTree(vector::iterator PreBegin, vector::iterator PreEnd, vector::iterator InBegin, vector::iterator InEnd) { if (PreBegin == PreEnd) { return NULL; } int HeadValue = *PreBegin; TreeNode *HeadNode = new TreeNode(HeadValue); vector::iterator LeftEnd = find(InBegin, InEnd, HeadValue); if (LeftEnd != InEnd) { HeadNode->left = buildTree(PreBegin + 1, PreBegin + (LeftEnd - InBegin) + 1, InBegin, LeftEnd); } HeadNode->right = buildTree(PreBegin + (LeftEnd - InBegin) + 1, PreEnd, LeftEnd + 1, InEnd); return HeadNode; } public: TreeNode* buildTree(vector& preorder, vector& inorder) { if (preorder.empty()) { return NULL; } return buildTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end()); } }; ~~~ **四. 小结** 该题考察了基础概念,并不涉及过多的算法问题。
';