LeetCode 109. Convert Sorted List to Binary Search Tree

LeetCode 109. Convert Sorted List to Binary Search Tree

Description:

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  5

---

分析：

这道题可以参考108题将数组转换成二叉搜索树的代码，我也是利用它来完成这道题目。

首先遍历链表，将其链表值存入vector数组中，然后和108题一样将数组转换成二叉搜索树。
具体过程为：找出中间数，作为根节点，然后将数组分成两半，递归求解即可。

LeetCode上的Discuss有一个想法是将找出链表的中间节点：先初始化temp为head，然后用了一个循环，在循环里不断更新temp为temp = temp->next->next;，循环退出条件为temp != NULL && temp->next != NULL，得到链表的中间节点，然后递归左右链表。具体代码在文章底部。

代码如下：

// 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 == NULL) return NULL;
		if (head->next == NULL) return new TreeNode(head->val);
		int cnt = 0;
		vector<int> v;
		ListNode* temp = head;
		while (temp != NULL) {
			v.push_back(temp->val);
			temp = temp->next;
			cnt++;
		}
		return sortedArrayToBST(v);
	}
	TreeNode* sortedArrayToBST(vector<int>& nums) {
		if (nums.size() == 0) return NULL;
		if (nums.size() == 1) return new TreeNode(nums[0]);
		// 根节点
		int middle = nums.size() / 2;
		TreeNode* root = new TreeNode(nums[middle]);
		// 左子树/右子树
		vector<int> leftVectors(nums.begin(), nums.begin() + middle);
		vector<int> rightVectors(nums.begin() + middle + 1, nums.end());
		// 递归
		root->left = sortedArrayToBST(leftVectors);
		root->right = sortedArrayToBST(rightVectors);
		return root;
	}
};

Discuss:

#include <iostream>
#include <vector>
#include <malloc.h>
using namespace std;
// 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) {
		return sortedListToBST(head, NULL);
	}
private:
	TreeNode* sortedListToBST(ListNode* head, ListNode* tail) {
		if (head == tail) return NULL;
		if (head->next == tail) {
			TreeNode *root = new TreeNode(head->val);
			return root;
		}
		ListNode *mid = head, *temp = head;
		// 寻找中间节点
		while (temp != tail && temp->next != tail) {
			mid = mid->next;
			temp = temp->next->next;
		}
		TreeNode *root = new TreeNode(mid->val);
		root->left = sortedListToBST(head, mid);
		root->right = sortedListToBST(mid->next, tail);
		return root;
	}
};