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

[题](从中序与后序遍历序列构造二叉树_牛客题霸_牛客网 (nowcoder.com))

1. 代码

   /**
    * struct TreeNode {
    *  int val;
    *  struct TreeNode *left;
    *  struct TreeNode *right;
    *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    * };
    */
   class Solution {
       int indexMap;//根节点的在后序遍历的下标
       unordered_map<int, int> unorderedMap;
     public:
       /**
        * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
        *
        *
        * @param inorder int整型vector 中序遍历序列
        * @param postorder int整型vector 后序遍历序列
        * @return TreeNode类
        */
           TreeNode *build(vector<int> &inorder, vector<int> &postorder, int leftSub, int rightSub) {
           if (leftSub > rightSub) {
               return nullptr;
           }
           auto root = new TreeNode(postorder[indexMap]);
           auto index = unorderedMap[postorder[indexMap]];
           indexMap--;
           root->right = build(inorder, postorder, index + 1, rightSub);
           root->left = build(inorder, postorder, leftSub, index - 1);
           return root;
       }
       TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
           // write code here
           indexMap = postorder.size() - 1;
           int sub = 0;
           for (const auto& item : inorder) {
               unorderedMap[item] = sub++;
           }
           return build(inorder, postorder, 0, inorder.size() - 1);
       }
   };

2. 提示

   • 后序遍历的最后一个元素是root的val

   • 采取递归的方法，创建结点

   • 注意创建的顺序，应该是先是右的再左的

     因为创建的顺序应该是是从最小树开始创建

3. 理解

   •         for (const auto& item : inorder) {
                 unorderedMap[item] = sub++;
             }
     

     将<元素，下标>的方式存放数据

     这样操作的原因是：方便的通过后序遍历找到root，再通过map查找数据

   • 把每一个都当成一个root

4. 问题

   • leftSub > rightSub

     当左节点的下标大于右节点的下标就表示这棵树是NULL

     也就是说子串是无的

   • 为什么要先创建右节点

     因为我们的后序遍历顺序是:左-右-根

     所以当我们把root取出剩下的应该就是右节点