LeetCode105—Construct Binary Tree from Preorder and Inorder Traversal

不念不忘少年蓝@ 2022-07-28 04:07 17阅读 0赞

# LeetCode105—Construct Binary Tree from Preorder and Inorder Traversal #

## 原题 ##

> Given preorder and inorder traversal of a tree, construct the binary tree.

给出树的先序和中序遍历，构建二叉树。

## 分析 ##

这题以前数据结构考试题中用，先序遍历可以可以找出树的根，中序遍历可以找出树的左右子树，如此递归下去，可以构建树。  
根据此：  
1. 在先序遍历中找到根  
2. 在中序遍历中找到根对应的位置，即可把中序分为左右两子树  
3. 计算在先序遍历中，分别计算左右子树中根的位置  
4. 递归左右子树

关于第2点，我们需要提前建立一个map来找出根和中序遍历中索引的对应关系。

## 代码 ##

class Solution {
    private:
        TreeNode* helper(vector<int>&preorder, vector<int>&inorder, map<int, int>&index, int pstart, int pend, int istart, int iend)
        {
            if (istart > iend)
                return NULL;
            int rootval = preorder[pstart];//根
            int rootindex = index[rootval];//根在中序中的索引
            TreeNode* root = new TreeNode(rootval);
            root->left = helper(preorder, inorder, index, pstart + 1, pstart + rootindex - istart, istart, rootindex - 1);//递归左子树
            root->right = helper(preorder, inorder, index, pstart + rootindex - istart + 1, pend, rootindex + 1, iend);//递归右子树
            return root;
        }
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            map<int, int>index;
            for (int i = 0; i < inorder.size(); i++)
            {
                index[inorder[i]] = i;//建立值与索引的关系
            }
            return helper(preorder, inorder, index,0, preorder.size() - 1, 0, inorder.size() - 1);
        }
    };//一定要使用引用否则会超时

这里传参数时一定要使用引用否则会超时。