力扣106. 从中序与后序遍历序列构造二叉树

栈

• 思路：
  • 思路与 力扣105. 从前序与中序遍历序列构造二叉树 相同；
  • 差异的地方：
    • 从后序遍历数组尾部向前遍历；（根节点在尾部）
    • 一直迭代“最右”节点，将其挂载到栈顶（“根”节点）的右子树节点；（后序遍历从尾部迭代顺序变成了：根-右子树-左子树）
    • 出栈后，挂载左子树；

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (!postorder.size()) {
            return nullptr;
        }

        int post_size = postorder.size();

        std::stack<TreeNode*> stk;
        TreeNode* root = new TreeNode(postorder[post_size - 1]);
        stk.push(root);

        int in_idx = post_size - 1;
        for (int idx = post_size - 2; idx >= 0; --idx) {
            TreeNode *node = stk.top();
            int post_val = postorder[idx];

            if (node->val != inorder[in_idx]) {
                node->right = new TreeNode(post_val);
                stk.push(node->right);
            } else {
                while (!stk.empty() && (stk.top()->val == inorder[in_idx])) {
                    node = stk.top();
                    stk.pop();
                    --in_idx;
                }
                node->left = new TreeNode(post_val);
                stk.push(node->left);
            }
        }

        return root;
    }
};