力扣106-数据结构经典作业:从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。
示例1

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例2
输入：inorder = [-1], postorder = [-1]
输出：[-1]
提示：
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

力扣题目链接

思路

写代码之前我们要先保证自己能过根据中序遍历&后序遍历构造出原二叉树：
以后序遍历数组的最后一个元素为切割点，先切割中序遍历数组，然后根据中序遍历数组切割后序遍历数组。如此往复，每次后续数组中的最后一个元素为切割点。当数组大小为1时，直接返回其值为该子树根节点。（分割后的前段构造左子树，后段构造右子树）
示例1流程如下：
中序：9，3，15，20，7
后序：9，15，7，20，3
后续数组最后一个元素为： 3 切割之后
中序前段：9 中序后段：15，20，7
后序前段：9 后序后段：15，7，20
此时应当注意到中序数组切割与后序数组切割后的大小是相同的
前段数组长度为1则直接返回，继而对后段数组对进行重复操作
切割点为：20
中序前段：15 中序后段：7
后序前段：15 后序后段：7
前后段数组元素数都为 1 ，二叉树构造完成

   3
  /   \
 9    20
     /   \
    15    7

图示可能更好理解（图源：代码随想录 点击前往 ）

代码实现

很明显，这是一个递归的逻辑；我们采取的是前序遍历，首先确定中间节点，然后递归构造左、右子树。那么下面我们按照递归三要素一步步来实现代码。

• 首先确定递归函数的参数和返回值
  传入中后续遍历数组，返回指向节点的指针。

  TreeNode* traversal (vector<int>& inorder, vector<int>& postorder)

• 确定终止条件
  如果遍历数组为空，那么直接返回null，表示该子树为空
  如果遍历数组中只有一个元素，那么该节点为叶子节点，该子树构造完成，直接返回

  if(postorder.size() == 0) {
  return nullptr;
  }
  int rootValue = postorder[postorder.size() - 1];
  TreeNode* node = new TreeNode(rootValue);
  if(postorder.size() == 1){
  return node;
  }

• 确定单层遍历逻辑
  找到切割点，即后序遍历数组最后一个元素,并切割中序、后序遍历数组

  int delimitIndex;
  for(delimitIndex = 0; delimitIndex < inorder.size(); delimitIndex++){
  if(inorder[delimitIndex] == rootValue){
    break;
  }
  }
  vector<int> leftInorder (inorder.begin(),inorder.begin() + delimitIndex);
  vector<int> rightInorder (inorder.begin() + delimitIndex + 1, inorder.end());
  postorder.resize(postorder.size() - 1);//舍弃后序遍历数组末尾元素，作为分割点已经参与构造
  vector<int> leftPostorder (postorder.begin(),postorder.begin() + leftInorder.size());
  vector<int> rightPostorder (postorder.begin() + leftInorder.size(), postorder.end());

  这里需要特别注意数组切割的边界值问题，一定要使用一致的划分原则。上述代码中我使用的是左闭右开级 [0, delimiterIndex)
  接下便可以进入递归逻辑

  node->left = traversal(leftInorder,leftPostorder);
  node->right = traversal(rightInorder,rightPostorder);

  下面是完整代码

  class Solution {
  private:
    TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return NULL;
  
        // 后序遍历数组最后一个元素，就是当前的中间节点
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);
        if (postorder.size() == 1) return root;
  
        // 找到中序遍历的切割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
  
        // 切割中序数组
        // 左闭右开区间：[0, delimiterIndex)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        // [delimiterIndex + 1, end)
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
  
        // postorder 舍弃末尾元素
        postorder.resize(postorder.size() - 1);
  
        // 切割后序数组
        // 依然左闭右开，注意这里使用了左中序数组大小作为切割点
        // [0, leftInorder.size)
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        // [leftInorder.size(), end)
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
  
        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);
  
        return root;
    }
  public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
  };