https://leetcode.com/PRoblems/convert-sorted-list-to-binary-search-tree/?tab=Description Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
思想同數組convert sorted array to binary search tree，只是鏈表只能順序遍歷。
struct TreeNode* toBST(struct ListNode* head, int n){ if (n == 0) { return NULL; } struct ListNode *p; struct TreeNode *node; int mid; int i; p = head; mid = n/2; for (i = 0; i < mid; ++i) { p = p->next; } node = (struct TreeNode *)malloc(sizeof(struct TreeNode)); node->val = p->val; node->left = toBST(head, mid); p = p->next; node->right = toBST(p, n-mid-1); return node; }struct TreeNode* sortedListToBST(struct ListNode* head) { if (head == NULL) { return NULL; } int n = 0; struct ListNode* p; p = head; while(p != NULL) { ++n; p = p->next; } return toBST(head, n);}C語言
struct TreeNode *toBST(struct ListNode **head, int n) { if(n == 0) { return NULL; } /* int mid; struct TreeNode *node; node = (struct TreeNode *)malloc(sizeof(struct TreeNode)); node->left = toBST(head, mid); node->val = head->val; head = head->next; node->right = toBST(head, n-mid-1); return node; */ int mid; struct TreeNode *c, *p; //struct ListNode *h; mid = n/2; c = toBST(head, mid); p = (struct TreeNode *)malloc(sizeof(struct TreeNode)); p->val = (*head)->val; p->left = c; *head = (*head)->next; p->right = toBST(head, n-mid-1); return p;}struct TreeNode* sortedListToBST(struct ListNode* head) { if (head == NULL) { return NULL; } int n = 0; struct ListNode* p; p = head; while(p != NULL) { ++n; p = p->next; } return toBST(&head, n);}新聞熱點
疑難解答
