【Leetcode】Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
昇順に並べられたチェーンテーブルを指定し、バランスのとれた二分ルックアップツリーに変換します.
まずこのチェーンテーブルの長さを求めることができ,中間のノードはバランスBSTのルートノードであり,チェーンテーブルを二つに分けて左右のサブツリーを再帰的に構築する.

class Solution {
public:
	TreeNode *sortedListToBST(ListNode *head) 
	{
		int nodeNum = 0;
		ListNode *node = head;
		while (node)
		{
			nodeNum++;
			node = node->next;
		}
		
		return sortedList2BST(head, nodeNum);
	}

	TreeNode *sortedList2BST(ListNode *head, int nodeNum)
	{
		if (nodeNum == 0)
			return NULL;

		int leftnum = nodeNum/2;
		int rightnum = nodeNum - leftnum - 1;

		ListNode *midnode = head;
		for (int i=0; i<leftnum; ++i)
			midnode = midnode->next;
		
		TreeNode *root = new TreeNode(midnode->val);

		root->left = sortedList2BST(head,leftnum);
		root->right = sortedList2BST(midnode->next, rightnum);
	}
};

ツリーを構築する過程で、元のチェーンテーブルの構造は変更されていないことに注意してください.