首页 > 代码库 > leetcode -day19 Convert Sorted List to Binary Search Tree
leetcode -day19 Convert Sorted List to Binary Search Tree
1、
Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
分析:将一个升序排列的链表转换为平衡二叉搜索树,采用递归的方式,先找到链表的中点,作为二叉树的根,然后递归求解左右子树。
如下:
class Solution { public: TreeNode *sortedListToBST(ListNode *head) { if(!head){ return NULL; } if(!head->next){ return new TreeNode(head->val); } ListNode* midNode = findMidNode(head); TreeNode* root = new TreeNode(midNode->val); TreeNode* leftSubTree = sortedListToBST(head); TreeNode* rightSubTree = sortedListToBST(midNode->next); if(leftSubTree){ root->left = leftSubTree; } if(rightSubTree){ root->right = rightSubTree; } return root; } ListNode* findMidNode(ListNode* head){ ListNode* node1 = head; if(!node1->next){ return node1; } ListNode* node2 = head->next; while(node2 && node2->next && node2->next->next){ node2 = node2->next; node2 = node2->next; node1 = node1->next; } ListNode* midNode = node1->next; node1->next = NULL; return midNode; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。