重建二叉树

发表于 | 分类于 | 评论数： | 阅读次数： | 阅读次数：

LeetCode 105. 重建二叉树from VLR && LVR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
TreeNode* buildTree (vector<int>& preorder, vector<int>& inorder) {
    return create (preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}
TreeNode* create (vector<int>& preorder, vector<int>& inorder, int ps, int pe, int is, int ie) {
    if (ps > pe) {
        return nullptr;
    }
    TreeNode* node = new TreeNode(preorder[ps]);
    int pos;
    for (int i = is; i <= ie; i++) {
        if (inorder[i] == node->val) {
            pos = i;
            break;
        }
    }
    node->left = create (preorder, inorder, ps + 1, ps + pos - is, is, pos - 1);
    node->right = create (preorder, inorder, pe - ie + pos + 1, pe, pos + 1, ie);
    return node;
}

Let me explain the coordinates in the recursion. Very simply, we can see that the inorder traversal is divided into two parts, [is, pos-1] and [pos+1, ie] according to the root node pointed by pos.The first part contains pos - is elements, and the second part has ie- (pos +1)+1 = ie - pos elements.
Correspondingly, in preorder traversal, the elements in the [ps+1, ps+pos - is] intervals belong to the left subtree, and the elements in the [pe - (ie - pos)+1, pe] interval belong to the right subtree.

LeetCode 106 重建二叉树from LVR && LRV

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
       return create (inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
   }
TreeNode* create (vector<int>& inorder, vector<int>& postorder, int is, int ie, int ps, int pe) {
    if (ps > pe) {
        return nullptr;
    }
    TreeNode* node = new TreeNode(postorder[pe]);
    int pos;
    for (int i = is; i <= ie; i++) {
        if (inorder[i] == node->val) {
            pos = i;
            break;
        }
    }
    node->left = create (inorder, postorder, is, pos - 1, ps, ps + pos - is - 1);
    node->right = create (inorder, postorder, pos + 1, ie, pe - ie + pos, pe - 1);
    return node;
}
0%