首页 > 代码库 > Convert Sorted List to Binary Search Tree
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.
分析: 根据一个有序链表,得到一个平衡二叉搜索树,主要是根据快慢指针得到链表的中点,然后将链表分成两半
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: ListNode* findMiddle(ListNode* start){ ListNode *low = start, *fast = start; ListNode* prelow=nullptr; while(fast!=nullptr){ fast = fast->next; if(fast){ fast = fast->next; prelow = low; low = low->next; } } if(prelow) prelow->next =nullptr;//break the list return low; } TreeNode* sortedListToBST(ListNode* head) { if(head==nullptr) return nullptr; if(head->next ==nullptr) return new TreeNode(head->val); ListNode* mid = findMiddle(head); TreeNode* root = new TreeNode(mid->val); root->left = sortedListToBST(head); root->right = sortedListToBST(mid->next); return root; } };
Convert Sorted List to Binary Search Tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。