leetcode 106 从中序与后序遍历序列构造二叉树

谁借莪１个温暖的怀抱￠ 2022-04-11 12:15 174阅读 0赞

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

## 题意 ##

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

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

例如，给出

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

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>& inorder, vector<int>& postorder) { 
            return driver(postorder, inorder, 0, postorder.size() - 1, 0, inorder.size() - 1);
        }
        TreeNode* driver(vector<int>& postorder, vector<int>& inorder, int p_lo, int p_hi, int i_lo, int i_hi) { 
            if (p_lo > p_hi) return NULL;
            if (p_lo == p_hi) return new TreeNode(postorder[p_hi]);
            int node_val = postorder[p_hi];
            int index_in = this->find(inorder, i_lo, i_hi, node_val);
            int pre_left_len = index_in - i_lo;
            TreeNode* node = new TreeNode(node_val);
            node->left = driver(postorder, inorder, p_lo, p_lo + pre_left_len - 1, i_lo, index_in - 1);
            node->right = driver(postorder, inorder, p_lo + pre_left_len, p_hi - 1, index_in + 1, i_hi);
            return node;
        }
        int find(vector<int>& vec, int low, int high, int val) { 
            for (int i = low; i <= high; ++i) { 
                if (vec[i] == val) return i;
            }
            return -1;
        }
    };

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