一. 題目描述
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());
}
};
四. 小結
該題考察了基礎概念,並不涉及過多的算法問題。