LeetCode-Construct Binary Tree from Preorder and Inorder Traversal
3506 ワード
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
注意:再帰アルゴリズムを使用して問題を解くときは、メモリの節約に注意してください.最初は下付きパラメータを渡すことで計算が面倒だと思っていたが、vectorデータを再構築するたびにパラメータを渡すことを試みた.以下に示す.
このようにするには2つの問題があります.1.反復器でvectorを初期化する場合、2番目の反復器は有効なデータの次の数を指します.2.メモリオーバーフローの問題が発生しやすい.(leetcodeで実行中にこの問題が発生しました).
Note: You may assume that duplicates do not exist in the tree.
class Solution {
public:
TreeNode * buildTree(vector<int>& preorder, int preBegin, int preEnd, vector<int>& inorder, int inBegin, int inEnd)
{
TreeNode*root =NULL;
if (preEnd >= preBegin)
{
root = new TreeNode(preorder[preBegin]);
int n = inEnd-inBegin+1;
int rootIndex = 0;
for (int i = inBegin; i <= inEnd; ++i)
{
if (inorder[i] == preorder[preBegin])
{
rootIndex = i;
break;
}
}
if (rootIndex!=inBegin)
{
root->left = buildTree(preorder, preBegin+1, preBegin+(rootIndex-inBegin), inorder, inBegin, rootIndex-1);
}
if (rootIndex!=inEnd)
{
root->right = buildTree(preorder, preBegin+1+(rootIndex-inBegin), preEnd, inorder, rootIndex+1, inEnd);
}
}
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTree(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
}
};
注意:再帰アルゴリズムを使用して問題を解くときは、メモリの節約に注意してください.最初は下付きパラメータを渡すことで計算が面倒だと思っていたが、vectorデータを再構築するたびにパラメータを渡すことを試みた.以下に示す.
if (rootIndex!=0)
{
vector<int>p(preorder.Begin()+1, preorder.Begin()+rootIndex+1);
vector<int>q(inorder.Begin(), inorder.Begin()+rootIndex);
root->left = buildTree(p,q);
}
このようにするには2つの問題があります.1.反復器でvectorを初期化する場合、2番目の反復器は有効なデータの次の数を指します.2.メモリオーバーフローの問題が発生しやすい.(leetcodeで実行中にこの問題が発生しました).