首页 > 代码库 > 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; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。