109. Convert Sorted List to Binary Search Tree

2019-11-10 18:38:02

字体：大中小

来源：转载

供稿：网友

跟上一题一样只是变成链表，遍历求中间值

/** * 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: TreeNode* build(ListNode* left, ListNode* right){ if (right == NULL && left == NULL){ return NULL; } if (right != NULL && right -> next == left){ return NULL; } ListNode* PReLeft = new ListNode(0); preLeft -> next = left; ListNode* tempNode = left; ListNode* preMiddleNode = preLeft; while (tempNode != right && tempNode -> next != right){ preMiddleNode = preMiddleNode -> next; tempNode = tempNode -> next -> next; } ListNode* middleNode = preMiddleNode -> next; TreeNode* root = new TreeNode(middleNode -> val); root -> left = build(left, preMiddleNode); root -> right = build(preMiddleNode -> next -> next, right); return root; } TreeNode* sortedListToBST(ListNode* head) { if(head == NULL) return NULL; return build(head, NULL); }};

上一篇：leetcode 2.Add Two Numbers

下一篇：约瑟夫环利用伪链表