根据前序和后序遍历构造二叉树、从前序与中序遍历序列构造二叉树、从中序与后序遍历序列构造二叉树、前序遍历构造二叉搜索树

✅ 构造二叉树系列

相关例题：

1008. 前序遍历构造二叉搜索树

题意：根据前序遍历结果构造二叉搜索树

img

1
2
输入：preorder = [8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]

1️⃣ buildTree · 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        int i;
        for (i = left + 1; i <= right; i++) {
            if (preorder[i] > preorder[left])
                break;
        }
        TreeNode* _left = buildTree(preorder, left + 1, i - 1);
        TreeNode* _right = buildTree(preorder, i, right);
        return new TreeNode(preorder[left], _left, _right);
    }

    TreeNode* bstFromPreorder(vector<int>& preorder) {
        if (preorder.empty())
            return nullptr;
        return buildTree(preorder, 0, preorder.size() - 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        if (preorder.empty())
            return nullptr;
        int i = upper_bound(preorder.begin() + 1, preorder.end(), preorder[0]) - preorder.begin();
        vector<int> preleft(preorder.begin() + 1, preorder.begin() + i);
        vector<int> preright(preorder.begin() + i, preorder.end());
        TreeNode* left = bstFromPreorder(preleft);
        TreeNode* right = bstFromPreorder(preright);
        return new TreeNode(preorder[0], left, right);
    }
};

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

img

1
2
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

1️⃣ 递归

LC106-c.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.empty())
            return nullptr;
        int i = ranges::find(inorder, postorder.back()) - inorder.begin();
        vector<int> in1(inorder.begin(), inorder.begin() + i);
        vector<int> in2(inorder.begin() + i + 1, inorder.end());
        vector<int> post1(postorder.begin(), postorder.begin() + i);
        vector<int> post2(postorder.begin() + i, postorder.end() - 1);
        TreeNode* left = buildTree(in1, post1);
        TreeNode* right = buildTree(in2, post2);
        return new TreeNode(postorder.back(), left, right);
    }
};

105. 从前序与中序遍历序列构造二叉树

img

1
2
3

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

1️⃣ 递归

lc105-c.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty())
            return nullptr;
        int i = ranges::find(inorder, preorder[0]) - inorder.begin();
        vector<int> pre1(preorder.begin() + 1, preorder.begin() + i + 1);
        vector<int> pre2(preorder.begin() + i + 1, preorder.end());
        vector<int> in1(inorder.begin(), inorder.begin() + i);
        vector<int> in2(inorder.begin() + i + 1, inorder.end());
        TreeNode* left = buildTree(pre1, in1);
        TreeNode* right = buildTree(pre2, in2);
        return new TreeNode(preorder[0], left, right);
    }
};

889. 根据前序和后序遍历构造二叉树

如果存在多个答案，您可以返回其中 任何 一个。

img

1
2
输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

1️⃣ 递归

首先说明，如果只知道前序遍历和后序遍历，这棵二叉树不一定是唯一的，如下图。

lc889-1.png

题目说，如果存在多个答案，我们可以返回其中任何一个。那么不妨规定：无论什么情况，在前序遍历中，preorder[1] 都是左子树的根节点值。

lc889-2-c.png

递归边界：

  • 如果 preorder 的长度是 0，对应着空节点，返回空。
  • 如果 preorder 的长度是 1，对应着二叉树的叶子，创建一个叶子节点并返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        if (preorder.empty()) {
            return nullptr;
        }
        if (preorder.size() == 1) {
            return new TreeNode(preorder[0]);
        }
        int left_size = find(postorder.begin(), postorder.end(), preorder[1]) - postorder.begin() + 1;
        vector<int> pre1(preorder.begin() + 1, preorder.begin() + left_size + 1);
        vector<int> pre2(preorder.begin() + left_size + 1, preorder.end());
        vector<int> post1(postorder.begin(), postorder.begin() + left_size);
        vector<int> post2(postorder.begin() + left_size, postorder.end() - 1);
        TreeNode* root = new TreeNode(preorder[0]);
        root->left = constructFromPrePost(pre1, post1);
        root->right = constructFromPrePost(pre2, post2);
        return root;
    }
};
许可协议

本文由 Yikun Wu 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处

分享文章
✍️ Yikun Wu 已发表了 69 篇文章 · 总计 293k 字，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处

🌀 本站总访问量 次