LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 后序遍历的最后一个元素即为树的根节点，根据此节点在中序遍历的位置划分左右子树即可

postorder = [9, 15, 7, 20, 3]
inorder =   [9, 3, 15, 20, 7]

在 inorder 中，3 的左侧即为左子树，右侧即为右子树
将 inorder 分为 [9] 和 [15, 20, 7] 两部分
将 postorder 分为 [9] 和 [15, 7, 20] 两部分

  3
 / \
9  15 20 7

postorder = [9]
inorder =   [9]
在 inorder 中查找 9，左右无元素

postorder = [15, 7, 20]
inorder =   [15, 20, 7]
在 inorder 中查找 20，左侧为 15，右侧为 7

  3
 / \
9  20
  /  \
 15   7

查找 15，左右无元素
查找 7，左右无元素
结束

• 解法如下

class Solution {
 public:
  TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    return buildTree(postorder, 0, postorder.size(), inorder, 0,
                     inorder.size());
  }

  TreeNode* buildTree(vector<int>& postorder, int l1, int r1,
                      vector<int>& inorder, int l2, int r2) {
    if (l1 >= r1 || l2 >= r2) {
      return nullptr;
    }
    TreeNode* t = new TreeNode(postorder[r1 - 1]);
    int pos =
        find(inorder.begin() + l2, inorder.begin() + r2, postorder[r1 - 1]) -
        inorder.begin();
    t->left = buildTree(postorder, l1, l1 + pos - l2, inorder, l2, pos);
    t->right =
        buildTree(postorder, l1 + pos - l2, r1 - 1, inorder, pos + 1, r2);
    return t;
  }
};