（树）根据排序数组或者排序链表重新构建BST树

题目一：给定一个数组，升序数组，将他构建成一个BST
思路：升序数组，这就类似于中序遍历二叉树得出的数组，那么根节点就是在数组中间位置，找到中间位置构建根节点，然后中间位置的左右两侧是根节点的左右子树，递归的对左右子树进行处理，得出一颗BST

代码：

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    TreeNode *sortedArrayToBST(vector<int> &num) {

        return sortedArrayToBST(, num.size()-, num);

    }

    TreeNode *sortedArrayToBST(int left, int right, vector<int> &num){

        if (left > right)

            return NULL;

        int mid = (left + right)/ + (left + right)% ;

        TreeNode *root = new TreeNode(num[mid]);

        root->left = sortedArrayToBST(left, mid-, num);

        root->right = sortedArrayToBST(mid+, right, num);

        return root;

    }

};

题目二：和第一题类似，只不过数组变成了链表。

代码：

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    TreeNode *sortedListToBST(ListNode *head) {

        vector<int> num;

        if (head == NULL)

            return NULL;

        while (head){

            num.push_back(head->val);

            head = head->next;

        }

        return sortListToBST(, num.size()-, num);

    }

    TreeNode *sortListToBST(int start, int end, vector<int> &num){

        if (start > end)

            return NULL;

        int mid = (end + start)/ + (end + start)%;

        TreeNode *root = new TreeNode(num[mid]);

        root->left = sortListToBST(start, mid-, num);

        root->right = sortListToBST(mid+, end, num);

        return root;

    }

};

巴特西

（树）根据排序数组或者排序链表重新构建BST树

最新文章

热门文章