leetcodeノート: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.
二.テーマ分析
この問題は、ルートノードに先にアクセスし、左サブツリーにアクセスし、最後に右サブツリーにアクセスする前シーケンスと中シーケンスの遍歴を考察した.中順ループは、まず左サブツリーをループし、次にルートノードにアクセスし、最後に右サブツリーにアクセスします.
方法は、まず、シーケンスループの概念に基づいて、シーケンスループの最初の値、すなわちルートノードの値を見つけ、ルートノードの点に基づいてシーケンスループの結果を左サブツリーと右サブツリーに分けて再帰的に実現します.
上記の方法によれば、時間的複雑度は
三.サンプルコード
四.小結
この問題は基礎概念を考察し,あまりアルゴリズムの問題に関与していない.
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 <iostream>
#include <algorithm>
#include <vector>
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<int>::iterator PreBegin, vector<int>::iterator PreEnd,
vector<int>::iterator InBegin, vector<int>::iterator InEnd)
{
if (PreBegin == PreEnd)
{
return NULL;
}
int HeadValue = *PreBegin;
TreeNode *HeadNode = new TreeNode(HeadValue);
vector<int>::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<int>& preorder, vector<int>& inorder)
{
if (preorder.empty())
{
return NULL;
}
return buildTree(preorder.begin(), preorder.end(), inorder.begin(),
inorder.end());
}
};
四.小結
この問題は基礎概念を考察し,あまりアルゴリズムの問題に関与していない.