Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted linked list: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5A:
就是用slow runner 和fast runner 找到中间node。然后,循环调用左边,右边即可。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* sortedListToBST(ListNode* head) { if(!head) return nullptr; ListNode * header = new ListNode(0); header->next = head; ListNode * preSlow = header; ListNode * fast = head; while(fast && fast->next){ fast = fast->next->next; preSlow = preSlow->next; } TreeNode *pRoot = new TreeNode(preSlow->next->val); // slow->next is the middle point pRoot->right = sortedListToBST(preSlow->next->next); preSlow->next = nullptr; pRoot->left= sortedListToBST(header->next); delete header; return pRoot; } };
这个的核心就是,起步的时候, preSlow 就比fast 提前一个位置。
Mistakes:
------------------------第一遍水过, 第二遍 结果出现错误了。哎, --- 原因是, preSlow节点,刚开始设为head,但后来设为preSlow.next = null的时候, 如果原本的list只有2个node,就会丢掉后面的????????为什么呢?, 哦, 因为, preSlow那个时候,和slow指的是同一个对象!!!!!
--------最新方法,就是直接用了header, ---------好东西啊----------- ^_^
Learned:
No comments:
Post a Comment