好,二叉搜索树粉末登场,有关他的问题有这么几个,给你一个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;
}
};