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]