LeetCode#106

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

题目链接
前序、中序、后序遍历是二叉树最常见的三种遍历方式，它们的详解和区别在这篇博客里写过。
我们想要通过中序和后序遍历来获取整个树形结构，大概过程是这样的：

• 首先通过找规律我们能看出来，后序节点的最后一个即为根节点
• 我们在中序中找到根节点，就可以根据中节点来将中序分为左右两部分，而这两部分左右分别是根节点的左右子树
• 通过递归的方式，来不停缩小递归范围，最后找到左右子树皆为空的节点即为叶子节点
  附代码（核心位置已经写了注释）：

  /**
   * 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:
      int post;
      TreeNode* dfs(vector<int>& inorder,vector<int>& postorder,int pos1,int pos2)
      {
          int cur;
          bool flag = false;
          for(int i = pos1 ; i <= pos2 ; i ++)//在限定中序搜索范围后，查找是否有当前的后序节点
          {
              if(inorder[i] == postorder[post])
              {
                  cur = i;
                  flag = true;
                  break;
              }
          }
          if(flag == false)//如果没找到当前后续节点，则该后序节点不在当前子树中
              return nullptr;
          TreeNode* node = new TreeNode(postorder[post]);//找到了之后返回当前节点
          post--;//找到后继续搜索下一个后序节点
          node -> right = dfs(inorder,postorder,cur + 1,pos2);
          node -> left = dfs(inorder,postorder,pos1,cur - 1);
          return node;
      }
      TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {    
          post = inorder.size()-1;//指向后序节点的指针，初始化为后序的最后一个节点
          return dfs(inorder,postorder,0,inorder.size()-1);
      }
  };