LeetCode 109. 有序链表转换二叉搜索树(Convert Sorted List to
发布时间:2020-12-14 03:50:48 所属栏目:大数据 来源:网络整理
导读:题目描述 ? 给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树 每个节点? 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定的有序链表: [-10,-3,5,9],一个可能的答案是:[0,9,-10,nu
题目描述? 给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点?的左右两个子树的高度差的绝对值不超过 1。 示例: 给定的有序链表: [-10,-3,5,9],一个可能的答案是:[0,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
0
/ -3 9
/ /
-10 5
? 解题思路? 转换二叉搜索树分为以下两步:
? 代码? 1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x),next(NULL) {} 7 * }; 8 */ 9 /** 10 * Definition for a binary tree node. 11 * struct TreeNode { 12 * int val; 13 * TreeNode *left; 14 * TreeNode *right; 15 * TreeNode(int x) : val(x),left(NULL),right(NULL) {} 16 * }; 17 */ 18 class Solution { 19 public: 20 TreeNode* sortedListToBST(ListNode* head) { 21 if(head == NULL) return NULL; 22 if(head->next == NULL) return new TreeNode(head->val); 23 ListNode *fast = head,*slow = head,*pre = head; 24 while(fast->next && fast->next->next){ 25 fast = fast->next->next; 26 pre = slow; 27 slow = slow->next; 28 } 29 TreeNode *root = new TreeNode(slow->val); 30 if(slow != pre){ 31 pre->next = NULL; 32 root->left = sortedListToBST(head); 33 } 34 root->right = sortedListToBST(slow->next); 35 return root; 36 } 37 }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |