【Leetcode】105. Construct Binary Tree from Preorder and Inorder Traversal（有前序和中序遍历求出树的结构）

比眉伴天荒 2022-02-18 15:31 168阅读 0赞

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

**Note:**  
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
    inorder = [9,3,15,20,7]

Return the following binary tree:

3
       / \
      9  20
        /  \
       15   7

题目大意：

由二叉树的前序和中序遍历得出二叉树的结构。

解题思路：

对preorder进行依次遍历，确定当前的节点；对inorder需要找出当前节点的位置，将其分为两部分；

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            
            return buildTreehelper(preorder, 0, preorder.size(), inorder, 0, inorder.size());
            
        }
        
        TreeNode* buildTreehelper(vector<int>& preorder, int sp, int ep, vector<int>& inorder, int si, int ei){
            
            if(sp == ep) return nullptr;
            
            TreeNode* tmp = new TreeNode(preorder[sp]);
            int idx = find(inorder.begin()+si, inorder.begin()+ei, preorder[sp]) - inorder.begin() - si;
            // 此处依然遵循左开右闭原则
            tmp->left = buildTreehelper(preorder, sp+1, sp+1+idx, inorder, si, si+idx);
                
            tmp->right = buildTreehelper(preorder, sp+1+idx, ep, inorder, si+idx+1, ei);
                
            return tmp;
            
        }
        
    };