问题
给出一个元素以递增序列排序的单链表,将其转换为一棵高度平衡的二叉搜索树。
初始思路
二叉搜索树高度平衡,意味着左右子树的高度要平衡。根据二叉树左子树节点小于根节点,右子树节点大于根节点的性质:我们在待选节点中选择值为中位数的节点作为根节点,所有小于中位数的节点作为左子树,所有大于中位数的节点作为右子树,即可满足高度平衡的要求。由于题目给出的已经是排好序的单链表,我们只要每次选择中间的节点即可。然后通过递归处理左右子树,最终完成高度平衡二叉搜索树的构建。
最终完成代码如下:
class Solution {
enum ChildType
{
LEFT,
RIGHT
};
public:
TreeNode *sortedListToBST(ListNode *head)
{
if(!head)
{
return nullptr;
} ListNode* middle = FindMiddlePoint(head, nullptr); TreeNode* root = new TreeNode(middle->val); MakeSubTree(head, middle, root, LEFT);
MakeSubTree(middle->next, nullptr, root, RIGHT); return root;
} void MakeSubTree(ListNode* head, ListNode* end, TreeNode* parent, ChildType childType)
{
if(head == end)
{
return;
} ListNode* middle = FindMiddlePoint(head, end); TreeNode* treeNode = new TreeNode(middle->val); if(childType == LEFT)
{
parent->left = treeNode;
}
else
{
parent->right = treeNode;
} MakeSubTree(head, middle, treeNode, LEFT);
MakeSubTree(middle->next, end, treeNode, RIGHT);
} ListNode* FindMiddlePoint(ListNode* head, ListNode* end)
{
int length = ;
ListNode* node = head; while(node != end)
{
++length;
node = node->next;
} length /= ; node = head;
for(int i = ; i < length; ++i)
{
node = node->next;
} return node;
}
};
sortedListToBST
Judge Small和Judge Large皆顺利通过。