leetcode 105 从前序与中序遍历序列构造二叉树

迈不过友情╰ 2022-04-11 12:09 134阅读 0赞

## 题意 ##

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:  
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = \[3,9,20,15,7\]  
中序遍历 inorder = \[9,3,15,20,7\]  
返回如下的二叉树：

3
       / \
      9  20
        /  \
       15   7

--------------------

## 样例输入输出 ##

见上

--------------------

## 想法 ##

代码里有注释  
基本思想是递归分治，利用了先序遍历和中序遍历的特性。  
先序遍历的特性是：第一个访问的结点一定是根结点。（即数组第一个值是根结点的值）  
中序遍历的特性是：数组中的一个值（现结点），其左边的全部是现结点的左子树中的值，右边的全部是现结点的右子树中的值。

--------------------

## 代码 ##

/** * 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 buildTree(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
        }
        
        /**重载这个函数*/
        //表示 前序为preorder，从下标p_l到p_r，中序为inorder，下标从i_l到i_r构建 树
        TreeNode* buildTree(vector<int>& preorder, vector<int> inorder, int p_l, int p_r, int i_l, int i_r) { 
            // 递归的边界，子树为空或着只有一个结点
            if(p_l > p_r) return NULL;
            if(p_l == p_r) return new TreeNode(preorder[p_l]);
            int index = find(inorder, i_l, i_r, preorder[p_l]);//根节点在中序遍历中的位置
            TreeNode* node = new TreeNode(preorder[p_l]);
            int pre_left_len = index - i_l;//左子树的长度
            // preorder[p_l+1 ... p_l+pre_left_len]是先序数组中与现结点左子树对应的部分。
            // inorder[i_l ... index_in-1]是中序数组中与现结点左子树对应的部分。
            node->left = buildTree(preorder, inorder, p_l+1, p_l+pre_left_len, i_l, index - 1);
            // preorder[p_lo+1+pre_left_len ... p_r]是先序数组中与现结点左子树对应的部分。
            // inorder[index+1 ... i_r]是中序数组中与现结点左子树对应的部分。
            node->right = buildTree(preorder, inorder, p_l+pre_left_len+1, p_r, index+1, i_r);
            return node;
        }
        
        int find(vector<int>& inorder, int l, int r, int node_val) { 
            for(int i =l;i <= r;i++){ 
                if(inorder[i] == node_val) return i;
            }
            return -1;
        }
    };

--------------------