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
preorder = [3,9,20,15,7]
inorder =  [9,3,15,20,7]

 inorder 中,3 的左侧即为左子树,右侧即为右子树
 inorder 分为 [9]  [15,20,7] 两部分
 preorder 分为 [9]  [20,15,7] 两部分

  3
 / \
9  15 20 7

preorder = [9]
inorder  = [9]
 inorder 中查找 9,左右无元素

preorder = [20,15,7]
inorder  = [15,20,7]
 inorder 中查找 20,左侧为 15,右侧为 7

  3
 / \
9  20
  /  \
 15   7

查找 15,左右无元素
查找 7,左右无元素
结束
class Solution {
 public:
  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    return buildTree(preorder, 0, size(preorder), inorder, 0, size(inorder));
  }

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

1
 \
 2

上述两棵树的前序遍历均为 [1, 2],后序遍历均为 [2, 1]