leetcode 109. 有序链表转换二叉搜索树(Convert Sorted List to
发布时间:2020-12-14 04:32:27 所属栏目:大数据 来源:网络整理
导读:目录 题目描述: 示例: 解法: 题目描述: 给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树 每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定的有序链表: [-10,-3,5,9],
目录
题目描述:给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例:给定的有序链表: [-10,-3,5,9],一个可能的答案是:[0,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树: 0 / -3 9 / / -10 5 解法:/** * 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; }else if(head->next == NULL){ return new TreeNode(head->val); }else{ ListNode* node = new ListNode(0); node->next = head; ListNode* cur = node,* ltail = node; while(cur != NULL){ cur = cur->next; if(cur == NULL){ break; }else{ cur = cur->next; } if(cur != NULL){ ltail = ltail->next; } } // cout<<ltail->val<<endl; TreeNode* root = new TreeNode(ltail->next->val); root->right = sortedListToBST(ltail->next->next); ltail->next = NULL; root->left = sortedListToBST(head); return root; } } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |