首页 > 代码库 > leetcode第一刷_Convert Sorted List to Binary Search Tree

leetcode第一刷_Convert Sorted List to Binary Search Tree

好,二叉搜索树粉末登场,有关他的问题有这么几个,给你一个n,怎样求所有的n个节点的二叉搜索树个数?能不能把所有的这些二叉搜索树打印出来?

这道题倒不用考虑这么多,直接转就行了,我用的思想是分治,每次找到一半的位置,分离出中间节点,作为新子树的根节点,然后递归构造前半部分和后半部分。

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        if(head == NULL)
            return NULL;
        int len = 0;
        ListNode *p = head;
        while(p){
            len++;
            p = p->next;
        }
        int hlen = len/2;
        ListNode *pp = head, *pre = head;
        for(int i=0;i<hlen;i++){
            pre = pp;
            pp = pp->next;
        }
        ListNode *newHead = pp->next;
        pre->next = NULL;
        pp->next = NULL;
        TreeNode *root = new TreeNode(pp->val);
        if(pp != head)  root->left = sortedListToBST(head);
        if(newHead) root->right = sortedListToBST(newHead);
        return root;
    }
};