首页 > 代码库 > leetcode dfs Convert Sorted List to Binary Search Tree
leetcode dfs Convert Sorted List to Binary Search Tree
Convert Sorted List to Binary Search Tree
Total Accepted: 21420 Total Submissions: 78476My SubmissionsGiven a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
题意:把有序单链表转换为二叉查找树
思路:
用链表中心作为当作二叉树的根,
链表的前半段作为左子树、后半段作为右子树。
可用递归实现
复杂度:时间O(n* log n),空间O(log n)
TreeNode * dfs(ListNode *head, int size){ if(size <= 0) return NULL; if(size == 1) return new TreeNode(head->val); ListNode *cur = head; for(int i = 0; i < size/2; ++i){ cur = cur->next; } TreeNode *root = new TreeNode(cur->val); root->left = dfs(head, size/2); root->right = dfs(cur->next, size - size/2 - 1 ); return root; } TreeNode *sortedListToBST(ListNode *head) { ListNode *cur = head; int size = 0; while(cur){ ++size; cur = cur->next; } return dfs(head, size); }
leetcode dfs Convert Sorted List to Binary Search Tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。