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

题目

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

思路

• 首先数组大小为0，说明是空结点
• 如果不为空，那么去前序数组的最后一个元素作为节点元素
• 找到前序数组最后一个元素在中序数组的位置，作为切割点
• 舍弃前序数组的第一个元素
• 切割中序数组，切成中序左数组和中序右数组
• 由于中序左数组和中序右数组的数组长度都是和先序左数组和先序右数组的长度相同
• 切割先序数组，先序左数组和先序右数组
• 递归处理左区间和右区间

代码

/**
 * 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* traversal(vector<int>& inorder,vector<int>& preorder){
        // 数组大小为0 说明是空结点
        if(preorder.size() == 0)
        {
            return NULL;
        }
        // 取出后序数组的第一个元素 作为节点元素
        int rootValue = preorder[0];
        TreeNode* root = new TreeNode(rootValue);

        // 叶子节点
        if(preorder.size() == 1) return root;

        // 第三步 寻找切割点
        int d;
        for(d = 0; d < inorder.size(); d++)
        {
            if(inorder[d] == rootValue)
            {
                break;
            }
        }

        // 切割中序数组  得到中序左数组和中序右数组
        vector<int> leftInorder(inorder.begin(),inorder.begin() + d);
        vector<int> rightInorder(inorder.begin() + d + 1,inorder.end());

        // 丢弃前序数组的第一个元素
        vector<int>::iterator k = preorder.begin();
        preorder.erase(k);

        // 切割前序数组
        vector<int> leftPreorder(preorder.begin(),preorder.begin() + leftInorder.size());
        vector<int> rightPreorder(preorder.begin() + leftInorder.size() ,preorder.end());

        root->left = traversal(leftInorder,leftPreorder);
        root->right = traversal(rightInorder,rightPreorder);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(inorder.size() == 0|| preorder.size() == 0)
        {
            return NULL;
        }

        return traversal(inorder,preorder);
    }
};


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
56
57
58
59
60
61
62
63
64
65