算法力扣刷题记录 五十【106.从中序与后序遍历序列构造二叉树】和【105.从前序与中序遍历序列构造二叉树】

前言

记录 三十八的四、二叉树构建通过层序遍历的数组实现。

层序遍历中，某个节点下标是i，那么左孩子的下标2i+1，右孩子的下标2i+2。这是统一的规律。

那么通过中序序列和后序序列如何构造二叉树？通过中序序列和前序序列如何构造二叉树？通过前序序列和后序序列如何构造二叉树？

---

一、【106.从中序与后序遍历序列构造二叉树】题目阅读

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

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

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]
1
2

提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历
1
2
3
4
5
6
7

---

二、【106.从中序与后序遍历序列构造二叉树】思路获取

参考思路链接

拿到题目分析：尝试看某个元素左右相邻的数值规律，没有成型的思路，所以先通过参考学习思路。

1. 中序：左中右；后序：左右中。
2. 确定后序的最后一位一定是中间节点（整个树的根节点）。
3. 拿到中间节点，在中序中找中间节点的位置，该位置左边区间所有数值是它的左子树；该位置右边区间所有数值是它的右子树。以中间节点为界，分成左右两边区间。
4. 以左区间内容在后序中比较，确定后序数组中左右的分界；相应剩下的是右区间。
5. 深入左区间，重复2-4步骤，可以建立左子树；深入右区间，重复2-4步骤，可以建立右子树。
6. 核心：

• 后序数组确定中间节点；
• 中序数组以中间节点为界，划分左右区间；
• 以分出来的左右区间，确定后序左右子树的界限。再次重复。（这个重复就是递归逻辑）
  –

---

三、【106.从中序与后序遍历序列构造二叉树】代码实现

有了思路后，先尝试代码实现：

/**
 * 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() == 0) return nullptr;

        //终止条件，如果后序只有一个节点，是一个节点的树。
        TreeNode* root = new TreeNode(postorder[postorder.size()-1]);//创建根节点
        if(postorder.size() == 1) return root;//返回上一层，把这个创建的根节点返回去

        //在中序数组中分出左右两边子树，整个区间坚持左闭右闭。
        int index = 0;
        for(;index < inorder.size();index++){
            if(inorder[index] == postorder[postorder.size()-1]) break;
        }
        //左子树长度是index
        vector<int> lefttree_inorder;
        for(int i = 0;i < index;i++){
            lefttree_inorder.push_back(inorder[i]);
        }
        //右子树长度inorder.size()-index-1
        vector<int> righttree_inorder;
        for(int i = index+1,j = 0;i < inorder.size();i++){
            righttree_inorder.push_back(inorder[i]);
        }

        //从后序数组中找到左右区间的分界
        vector<int> lefttree_postorder;
        for(int i = 0;i < index;i++){//截取长度index
            lefttree_postorder.push_back(postorder[i]);
        }
        vector<int> righttree_postorder;
        for(int i = index;i < postorder.size()-1;i++){//从下标index开始，到最后一个元素之前
            righttree_postorder.push_back(postorder[i]);
        }

        //深入左子树和右子树
        TreeNode* leftroot = buildTree(lefttree_inorder,lefttree_postorder);
        TreeNode* rightroot = buildTree(righttree_inorder,righttree_postorder);
        root->left = leftroot;
        root->right = rightroot;
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

对比参考代码：

• 在中序数组分左右时：

   // 左闭右开区间：[0, delimiterIndex)
  vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
  // [delimiterIndex + 1, end)
  vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
  1
  2
  3
  4

• 在后序中分左右时：

  // postorder 舍弃末尾元素，因为这个元素就是中间节点，已经用过了
  postorder.resize(postorder.size() - 1);
  
  // 左闭右开，注意这里使用了左中序数组大小作为切割点：[0, leftInorder.size)
  vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
  // [leftInorder.size(), end)
  vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
  1
  2
  3
  4
  5
  6
  7

• 参考使用构造函数，遵循左闭右开区间规则；代码实现使用for循环填充元素，遵循左闭右闭区间规则。

改进【使用下标分割】

【使用下标分割】思路：

1. 上面每一次递归，分割数组都是建立4个新数组，开辟空间后，传递给下一层；
2. 使用同一个数组，每一层传入下标值，这样不用新建数组。
3. 不过8个下标要确认好。

【使用下标分割】代码实现

/**
 * 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* build(vector<int>& inorder,vector<int>& postorder,int inorder_left,int inorder_right,int postorder_left,int postorder_right){
        //左闭右开规则
        //终止条件,对应后序数组为空
        if(postorder_left == postorder_right) return nullptr;
        //终止条件，后序只有一个节点，是一个节点的树。
        TreeNode* root = new TreeNode(postorder[postorder_right-1]);
        if(postorder_right - postorder_left == 1) return root;

        //找中间节点在中序数组的位置
        int index = inorder_left;
        for(;index < inorder_right;index++){
            if(inorder[index] == postorder[postorder_right-1]) break;
        }
        //中序数组左区间：[inorder_left,index)。右区间：[index+1,inorder_right)
        int leftinorderbegin = inorder_left;
        int leftinorderend = index;
        int rightinorderbegin = index+1;
        int rightinorderend = inorder_right;
        //长度：index-inorder_left
        //找后序数组的左右分界：[postorder_left,postorder_left+index-inorder_left)。右区间传参：[postorder_left+index-inorder_left，postorder_right-1)
        int leftpostbegin = postorder_left;
        int leftpostend = postorder_left+index-inorder_left;
        int rightpostbegin = postorder_left+index-inorder_left;
        int rightpostend = postorder_right-1;

        root->left = build(inorder,postorder,leftinorderbegin,leftinorderend,leftpostbegin,leftpostend);
        root->right = build(inorder,postorder,rightinorderbegin,rightinorderend,rightpostbegin,rightpostend);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return build(inorder,postorder,0,inorder.size(),0,postorder.size());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

---

四、【105.从前序与中序遍历序列构造二叉树】题目阅读

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

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

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]
1
2

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列
1
2
3
4
5
6
7

---

五、【105.从前序与中序遍历序列构造二叉树】思路和代码实现

思路

和【106.通过中序和后序构建二叉树】基本一致，区别：前序的中在最前面。

代码实现1【创建数组】

/**
 * 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>& preorder, vector<int>& inorder) {
        //这个子树没有元素。说明空
        if(preorder.size() == 0) return nullptr;

        //子树只有一个元素
        TreeNode* root = new TreeNode( preorder[0]);
        if(preorder.size() == 1) return root;

        //子树有多个元素
        //拿着root的值去分割inorder
        int index = 0;  //index就是长度
        for(;index < inorder.size();index++){
            if(inorder[index] == preorder[0]) break;
        }
        //左闭右开
        vector<int> leftinorder(inorder.begin(),inorder.begin()+index);
        vector<int> rightinorder(inorder.begin()+index+1,inorder.end());

        //用左右区间分割前序数组
        vector<int> leftpreorder(preorder.begin()+1,preorder.begin()+1+index);
        vector<int> rightpreorder(preorder.begin()+1+index,preorder.end());

        root->left = buildTree(leftpreorder,leftinorder);
        root->right = buildTree(rightpreorder,rightinorder);
        return root;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

代码实现2【下标分割，不创建数组】

/**
 * 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* build(vector<int>& preorder,vector<int>& inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right){
        //这个子树没有元素。说明空
        if(preorder_left == preorder_right) return nullptr;

        //子树只有一个元素
        TreeNode* root = new TreeNode(preorder[preorder_left]);
        if(preorder_right - preorder_left == 1) return root;

        //子树有多个元素
        //拿着root的值去分割inorder
        int index = inorder_left;
        for(;index < inorder_right;index++){
            if(inorder[index] == preorder[preorder_left]) break;
        }
        //左闭右开
        int leftinorderbegin = inorder_left;
        int leftinorderend = index;
        int rightinorderbegin = index+1;
        int rightinorderend = inorder_right;

        //用左右区间分割前序数组
        int leftpreorderbegin = preorder_left+1;
        int leftpreorderend = preorder_left+1+index-inorder_left;
        int rightpreorderbegin = leftpreorderend;
        int rightpreorderend = preorder_right;

        root->left = build(preorder,inorder,leftpreorderbegin,leftpreorderend,leftinorderbegin,leftinorderend);
        root->right = build(preorder,inorder,rightpreorderbegin,rightpreorderend,rightinorderbegin,rightinorderend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder,inorder,0,preorder.size(),0,inorder.size());

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

---

总结

构造二叉树：

（欢迎指正，转载标明出处）