Reconstruct Tree

发表于 | 分类于

Construct Tree From Array

题目描述1：

给定树的不同的遍历方式来重建树。第一种是根据先序遍历和中序遍历的结果来重建树。

例子：

这道题是leetcode上的题目,具体描述可以看这个。

解题思路：

根据先序遍历的结果我们可以知道树的根节点，根据中序遍历中该根节点的位置，我们可以知道左右子树的节点。假设先序遍历的结果是[1,2,4,5,3,6,7],中序遍历的结果是[4,2,5,1,6,3,7]。我们根据先序遍历的第一个节点是1，所以知道左子树的节点集合是[4,2,5],右子树的节点集合是[6,3,7];然后根据左子树的长度是3知道[2,4,5]是对应左子树的先序遍历的结果;而[3,6,7]则是右子树的先序遍历的结果。如此不断递归构建即可得到树的结果。

代码如下：

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
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0) return NULL;
        return generate(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
    TreeNode* generate(vector<int>& preorder, vector<int>& inorder, int p_left, int p_right, int i_left, int i_right){
    //构建树的函数里面有6个参数，主要是先序遍历结果，中序遍历结果以及当前构建树对应节点在遍历结果的开始位置和结束位置
    //p_left表示先序遍历的起始，p_right表示先序遍历的结束
    //i_left表示中序遍历的起始，i_right表示中序遍历的结束
        if (p_left == p_right){
            return new TreeNode(preorder[p_left]);
        }
        //如果起始和结束位置相同，表示只有一个节点，直接新建节点返回
        if (p_left > p_right) return NULL;
        //如果起始超过结束，表示无节点，即为空节点
        int next = 0;
        for (int i = i_left; i <= i_right; i++){
            if (inorder[i] == preorder[p_left]) {
                next = i;
                break;
            }
        }
        //找到先序遍历起始节点在中序遍历中的位置，用next保存
        
        int left_length = next - i_left;
        //计算左子树的长度
        TreeNode* root = new TreeNode(inorder[next]);
        //新建根节点用起始节点的数值
        root->left = generate(preorder, inorder, p_left + 1, p_left + left_length, i_left, next - 1);
        //递归调用函数来构建树，主要需要注意关于树的起始位置和结束位置的变化
        root->right = generate(preorder, inorder, p_left + left_length + 1, p_right, next + 1, i_right);
        return root;        
    }
};

题目描述2：

当然，也可以根据中序遍历和后序遍历来重建树。解题的思路和上一题类似，我们主要需要注意的是，在递归函数中，起始位置和终止位置的变化如何计算的问题。

例子：

这题也是leetcode上的题目.

代码实现:

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
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0) return NULL;
        return generate(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
        
    }
    TreeNode* generate(vector<int>& inorder, vector<int>& postorder, int i_left, int i_right, int p_left, int p_right){
        if (i_left == i_right){
            return new TreeNode(inorder[i_left]);
        }
        if(i_left > i_right){
            return NULL;
        }
        int next = 0;
        for (int i = i_left; i <= i_right; i++){
            if (inorder[i] == postorder[p_right]){
                next = i;
                break;
            }
        }
        int length = i_right - next;
        TreeNode* root = new TreeNode(inorder[next]);
        root->left = generate(inorder, postorder, i_left, next - 1, p_left, p_right - length - 1);
        root->right = generate(inorder, postorder, next + 1, i_right, p_right - length, p_right - 1);
        return root;
    }
};

题目描述3：

给定一个数字n，要求得到根据这个数字所得到的数组[1,2,3…..n]，从这个数组中构建搜索二叉树的个数。

例子：

给定数字假设为3，通过计算分别以1，2，3为头结点的有效的搜索二叉树的个数可以知道，其结果为5。

解题思路：

通过从1开始计算其可能的二叉树个数，可以发现规律：当n=1，二叉树的个数为1；当n=2的时候，二叉树的个数为2；当n=3的时候，二叉树的个数为5。分析n=3的情况：以1为头结点，用于构建左子树的数字为空，用于构建右子树的数字为[2,3]，所以总的个数为h(0) h(2) = 2；同理在以2为头结点的情况下，个数为h(1) h(1) = 1；以3为头结点情况，h(2) h(0) = 1;所以一共有5种。通过推广到n；我们用h(i)表示用i个数构建二叉树的个数，h(0)=1,h(1)=1,h(2)=2…则h(n) = h(n-1) h(0) + h(n-2) * h(1)…这样所得到的序列称为卡特兰数序列。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numTrees(int n) {
        vector<int>vec;
        vec.push_back(1);
        vec.push_back(1);
        vec.push_back(2);//定义初始的数
        for(int i = 3; i <= n; i++){
            int res = 0;
            for (int j = 1; j <= i; j++){
                res = res + vec[j - 1] * vec[i - j];
            }
            vec.push_back(res);//计算第i个位置的卡特兰数
        }
        return vec[n];
    }
};

题目描述4：

根据上一题的描述，我们要求返回所有有效的二叉树的头结点的集合。解题的思路，主要是利用递归构建树的想法，直接上代码。

代码如下：

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
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> res;
        if (n == 0) return res;
        return helper(1, n);
    }
    vector<TreeNode*>helper(int start, int end){
        vector<TreeNode*>res;
        //用来保存当前递归层的可能二叉树的头节点
        if (start > end) res.push_back(NULL);
        //此时直接构建空树
        if (start == end) res.push_back(new TreeNode(start));
        // 此时返回以当前数的节点
        if (start < end){
            for (int i = start; i <= end; i++){
            //遍历以当前范围中各个数为头结点的可能
                vector<TreeNode*>lefts = helper(start, i - 1);
                vector<TreeNode*>rights = helper(i + 1, end);
                //找到该情况下左右子树的头结点的集合
                for (int j = 0; j < (int)lefts.size(); j++){
                    for(int k = 0; k < (int)rights.size(); k++){
                        TreeNode* root = new TreeNode(i);
                        root->left = lefts[j];
                        root->right = rights[k];
                        //指向左右子树
                        res.push_back(root);
                        //保存结果
                    }
                }
            }
        }
        return res;
    }
};

题目描述5:

给定一个已经排序的数组，要求根据数组构建一棵平衡二叉搜索树.
具体的题目描述可以看LeetCode108。

解题思路：

因为要构建平衡二叉搜索树，所以我们可以从数组的中间取出作为根节点，然后递归的建立左右子树即可。

代码如下:

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
//构建平衡二叉搜索树
/**
 * 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 {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() == 0) return NULL;
        return constructTree(0, nums.size() - 1, nums);
        
    }
    TreeNode* constructTree(int low, int high, vector<int>& nums){
        if (low == high){
            TreeNode* p = new TreeNode(nums[low]);
            return p;
            //当left==right代表只剩下一个数用于构建树，所以直接构建新节点然后返回
        }
        if (low > high){
            return NULL;
        }
        //这种情况，说明已经没有节点用于构建树
        int mid = low + (high - low) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        //找到中间节点构建根节点
        root->left = constructTree(low, mid - 1, nums);
        root->right = constructTree(mid + 1, high, nums);
        //递归构建左右子树
        return root;
    }
};