`
cozilla
  • 浏览: 92067 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

[Leetcode] Convert Sorted List to Binary Search Tree

 
阅读更多
Convert Sorted List to Binary Search TreeOct 3 '125768 / 16298

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

 

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * 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;
        ListNode* t = head;
        int len = 0;
        while (t != NULL) len++, t = t->next;
        return gen(head, 0, len - 1);
    }
    
    TreeNode *gen(ListNode* &cur, int start, int end) {
        if (start > end) return NULL;
        int mid = start + (end -start) / 2;
        TreeNode *left = gen(cur, start, mid - 1);
        TreeNode *node = new TreeNode(cur->val);
        cur = cur->next;
        node->left = left;
        node->right = gen(cur, mid+1, end);
    }
};

 

分享到:
评论

相关推荐

    python-leetcode-109-Convert-Sorted-List-to-Binary-Search-Tree

    python python_leetcode_109_Convert_Sorted_List_to_Binary_Search_Tree

    js-leetcode题解之109-convert-sorted-list-to-binary-search-tree.js

    javascript js_leetcode题解之109-convert-sorted-list-to-binary-search-tree.js

    lrucacheleetcode-leetcode:leetcode

    lru缓存leetcode leetcode 大批 41. First Missing Positive 广度优先搜索 773. Sliding Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary...

    LeetCode最全代码

    * [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...

    leetcodelintcode差异-LeetcodeJava:LeetcodeJava

    leetcode lintcode差异 Lintcode 解题思路记录 Table of Contents Linked List Convert Sorted List to Binary Search Tree Given a singly linked list where elements are sorted in ascending order, convert it ...

    Leetcode book刷题必备

    30. Convert Sorted List to Balanced Binary Search Tree:将有序链表转换成平衡的二叉搜索树。 31. Binary Tree Maximum Path Sum:二叉树中的最大路径和。 32. Binary Tree Upside Down:将一个二叉树进行翻转。 ...

    leetcode卡-leetcode:利特码解决方案

    leetcode卡 leetcode exercises 3-5 solutions everyday. fighting~ TODO array Best Time to Buy and Sell Stock II Valid Sudoku linked list Palindrome linked list Linked List Cycle trees Convert Sorted ...

    Leetcode题目+解析+思路+答案.pdf

    - **Convert Sorted List/Array to Binary Search Tree**:将有序列表或数组转换为二叉搜索树。 - **Path Sum II**:寻找所有从根节点到叶节点的路径,其路径和等于给定的目标值。 - **Flatten Binary Tree to ...

    常见算法题答案及解析

    30. Convert Sorted List to Binary Search Tree:将有序链表转换为高度平衡的二叉搜索树。 31. Binary Tree Maximum Path Sum:二叉树中的最大路径和。 32. Binary Tree Upside Down:将二叉树进行上下翻转。 五、...

    java-leetcode题解之第109题有序链表转换二叉搜索树.zip

    在本压缩包中,我们关注的是Java编程语言与LeetCode平台上的第109题——有序链表转换为二叉搜索树(Convert Sorted List to Binary Search Tree)。这是一道涉及数据结构与算法的问题,主要涵盖了链表操作和二叉搜索...

    Leetcode答案(c++版)

    **1.9 Convert Sorted List to Binary Search Tree (109)** - **问题描述**:给定一个链表,将其转换为平衡二叉搜索树。 - **解题思路**: - 先找到链表的中间节点作为根节点。 - 使用递归方式处理左子树和右子树...

    lrucacheleetcode-LeetCode:LeetCode刷题

    把字符串转换成整数(Convert a string to an integer) 2018.10.8 树的子结构(Substructure of the tree) 2018.10.8 旋转数组的最小数字(Rotate The Smallest Number of Arrays) 2018.10.9 二叉搜索树的后序...

    算法-leetcode-剑指offer上的题很多

    - **整数转换(Convert Integer A to Integer B)**: 将一个整数转换为另一个整数。 - **阶乘末尾0的个数(Factorial Trailing Zeroes)**: 计算一个整数阶乘结果末尾有多少个零。 - **唯一二叉搜索树(Unique Binary ...

    Facebook 最新面试题总结

    Convert Binary Search Tree to Sorted Doubly Linked List(将二叉搜索树转换为排序的双链表)**: - 需要将二叉搜索树转换为双向链表,且链表中的节点按照排序顺序排列。 5. **LeetCode 56. Merge Intervals...

Global site tag (gtag.js) - Google Analytics