[LeetCode] 109. Convert Sorted List to Binary Search Tree

轉自LeetCode

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
<Solution>

這題和 Convert Sorted Array to Binary Search Tree 一樣

只是資料結構變成 linked list，所以在操作上會不同

先看 recursive 的解法

想法也是一樣，找到中間的node，然後左半部是左子樹，右半部是右子樹

用 recursive 方式把樹建出來

那 linked list 怎麼找到中間的node，利用兩個指針來達到

fast 指針一次移動兩個 node，slow指針一次移動一個 node

這樣當 fast 移動了 n 個 node 的時候，slow 只移動了 n/2，這樣就可以找到中間的node了

找到中間的node之後，再切出左半部和右半部，並 recursive 做下去即可

code 如下

	/**
	* 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* sortedListToBST(ListNode* head) {
	if(!head) {
	return NULL;
	}
	ListNode *dummy = new ListNode(0);
	dummy->next = head;
	ListNode *fast = head, *slow = dummy;
	//> find the mid node in current list
	while(fast->next && fast->next->next) {
	slow = slow->next;
	fast = fast->next->next;
	}
	TreeNode *rootNode = new TreeNode(slow->next->val);
	//> list of the right tree
	ListNode *rightTreeHead = slow->next->next;
	//> list of the left tree ends here
	slow->next = NULL;
	if(slow != dummy) {
	rootNode->left = sortedListToBST(head);
	}
	rootNode->right = sortedListToBST(rightTreeHead);
	return rootNode;
	}
	};

view raw convertSortedListToBinarySearchTree_1.cpp hosted with ❤ by GitHub

那一樣有 iterative 的解法，想法也是和 Convert Sorted Array to Binary Search Tree 一樣

用一個 queue 來存放要處理的 list，以及相對應的 tree node

每個循環，找到 list 中間的 node，將數值更新到對應的 tree node

然後再分左半部和右半部，繼續循環下去

code 如下

	/**
	* 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* sortedListToBST(ListNode* head) {
	if(!head) {
	return NULL;
	}
	TreeNode *root = new TreeNode(0); //> dummy value
	queue<pair<ListNode *, TreeNode *>> nodeQue;
	nodeQue.push({head, root});
	while(!nodeQue.empty()) {
	ListNode *dummy = new ListNode(0); //> dummy value
	dummy->next = nodeQue.front().first;
	//> find middle node of the list
	ListNode *slow = dummy, *fast = dummy->next;
	while(fast->next && fast->next->next) {
	slow = slow->next;
	fast = fast->next->next;
	}
	TreeNode *tmpRoot = nodeQue.front().second;
	nodeQue.pop();
	tmpRoot->val = slow->next->val;
	ListNode *rightTreeHead = slow->next->next; //> save list nodes for right tree
	//> left tree part of the list
	slow->next = NULL;
	if(slow != dummy) {
	tmpRoot->left = new TreeNode(0); //> dummy value
	nodeQue.push({dummy->next, tmpRoot->left});
	}
	//> right tree part of the list
	if(rightTreeHead) {
	tmpRoot->right = new TreeNode(0); //> dummy value
	nodeQue.push({rightTreeHead, tmpRoot->right});
	}
	}
	return root;
	}
	};

view raw convertSortedListToBinarySearchTree_2.cpp hosted with ❤ by GitHub