Sui Xin's Blog

[LeetCode] 105.从前序与中序遍历序列构造二叉树（Construct Binary Tree from Preorder and Inorder Traversal）

Posted on In Disqus:

题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

3

/ \

9 20

​ / \

15 7

解题思路

递归。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder) < 1:
            return None
        root = TreeNode(preorder[0])
        idx = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:idx + 1], inorder[:idx])
        root.right = self.buildTree(preorder[idx + 1:], inorder[idx + 1:])
        return root

执行用时 : 216 ms
内存消耗 : 87.5 MB

C++

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    unordered_map<int, int> index;

public:
    TreeNode* mybuildTree(vector<int>& preorder, vector<int>& inorder, int preorder_l, int preorder_r, int inorder_l, int inorder_r) {
        if (preorder_r <= preorder_l) return nullptr;

        int root_val = preorder[preorder_l];
        int root_idx = index[root_val];
        int left_num = root_idx - inorder_l;

        TreeNode* root = new TreeNode(root_val);
        root -> left = mybuildTree(preorder, inorder, preorder_l + 1, preorder_l + left_num + 1, inorder_l, inorder_l + left_num);
        root -> right = mybuildTree(preorder, inorder, preorder_l + left_num + 1, preorder_r, inorder_l + left_num + 1, inorder_r);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int len = preorder.size();
        for (int i = 0; i < len; ++i) {
            index[inorder[i]] = i;
        }
        return mybuildTree(preorder, inorder, 0, len, 0, len);
    }
};

执行用时 : 24 ms
内存消耗 : 17.7 MB

Related Posts