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

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

题目链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

题目

解答

一层一层切割

1. 如果数组长度为零，则说明是空节点
2. 如果数组不为空，那么将后序数组的最后一个元素作为节点元素
3. 找到后序数组的最后一个元素在中序数组中的位置并将其作为切割点
4. 切割中序数组，切成中序左数组和中序右数组
5. 切割后续数组，切成后序左数组和后序右数组
6. 递归处理左区间和右区间

后序数组不想中序数组有明确的切割点，此时有一个关键点，就是中序数组的长度一定和后序数组的长度相同。

class Solution {
private:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder){
        if(postorder.size() == 0)  return NULL;
        //后序遍历数组的最后一个元素就是当前的中间节点
        int rootValue = postorder[postorder.size() - 1];
        TreeNode*  root = new TreeNode(rootValue);

        //叶子节点
        if(postorder.size() == 1)   return root;
        //找到中序遍历的切割点
        int delimiterIndex;
        for(delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++){
            if(inorder[delimiterIndex] == rootValue){
                break;
            }
        }
        //切割中序数组
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end());
        //舍弃末尾元素
        postorder.resize(postorder.size() - 1);
        //切割后序数组
        vector<int> leftPostorder(postorder.begin() , postorder.begin() + leftInorder.size());
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() == 0 || postorder.size() == 0)    return NULL;
        return traversal(inorder, postorder);
    }
};
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

​ 上述代码的逻辑较为清晰，但是性能并不好，因为每层递归都定义了新的vector

​ 下面给出使用下标分割数组的代码版本

class Solution {
private:
    TreeNode* traversal(vector<int> inorder, int inorderBegin, int inorderEnd, vector<int> postorder, int postorderBegin, int postorderEnd){
        if(postorderBegin == postorderEnd)  return NULL;
        
        int rootValue = postorder[postorderEnd - 1];
        TreeNode* root = new TreeNode(rootValue);

        if(postorderEnd - postorderBegin == 1)  return root;

        int delimiterIndex;
        for(delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++){
            if(inorder[delimiterIndex] == rootValue){
                break;
            }
        }

        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd  = inorderEnd;

        int leftPostorderBegin = postorderBegin;
        int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin;
        int rightPostorderBegin = postorderBegin + delimiterIndex - inorderBegin;
        int rightPostorderEnd = postorderEnd - 1;

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() == 0 || postorder.size() == 0)    return NULL;
        return traversal(inorder, 0, inorder.size(), postorder, 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