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.
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で実行中にこの問題が発生しました).