C++实现LeetCode(109.将有序链表转为二叉搜索树)

[LeetCode] 109.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.

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

这道题是要求把有序链表转为二叉搜索树，和之前那道 Convert Sorted Array to Binary Search Tree 思路完全一样，只不过是操作的数据类型有所差别，一个是数组，一个是链表。数组方便就方便在可以通过index直接访问任意一个元素，而链表不行。由于二分查找法每次需要找到中点，而链表的查找中间点可以通过快慢指针来操作，可参见之前的两篇博客 Reorder List 和 Linked List Cycle II 有关快慢指针的应用。找到中点后，要以中点的值建立一个数的根节点，然后需要把原链表断开，分为前后两个链表，都不能包含原中节点，然后再分别对这两个链表递归调用原函数，分别连上左右子节点即可。代码如下：

解法一：

class Solution {
public:
    TreeNode *sortedListToBST(ListNode* head) {
        if (!head) return NULL;
        if (!head->next) return new TreeNode(head->val);
        ListNode *slow = head, *fast = head, *last = slow;
        while (fast->next && fast->next->next) {
            last = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        last->next = NULL;
        TreeNode *cur = new TreeNode(slow->val);
        if (head != slow) cur->left = sortedListToBST(head);
        cur->right = sortedListToBST(fast);
        return cur;
    }
};

我们也可以采用如下的递归方法，重写一个递归函数，有两个输入参数，子链表的起点和终点，因为知道了这两个点，链表的范围就可以确定了，而直接将中间部分转换为二叉搜索树即可，递归函数中的内容跟上面解法中的极其相似，参见代码如下：

解法二：

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return NULL;
        return helper(head, NULL);
    }
    TreeNode* helper(ListNode* head, ListNode* tail) {
        if (head == tail) return NULL;
        ListNode *slow = head, *fast = head;
        while (fast != tail && fast->next != tail) {
            slow = slow->next;
            fast = fast->next->next;
        }
        TreeNode *cur = new TreeNode(slow->val);
        cur->left = helper(head, slow);
        cur->right = helper(slow->next, tail);
        return cur;
    }
};

类似题目：

Convert Sorted Array to Binary Search Tree

参考资料：

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35476/Share-my-JAVA-solution-1ms-very-short-and-concise.

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35470/Recursive-BST-construction-using-slow-fast-traversal-on-linked-list

到此这篇关于C++实现LeetCode(109.将有序链表转为二叉搜索树)的文章就介绍到这了,更多相关C++实现将有序链表转为二叉搜索树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(145.二叉树的后序遍历)

    [LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历 Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3},    1 \ 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you d

  • C++实现LeetCode(101.判断对称树)

    [LeetCode] 101.Symmetric Tree 判断对称树 Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric:     1 / \ 2   2 / \   / \ 3  4 4  3 But the following is not:     1 / \ 2  

  • C++实现LeetCode(104.二叉树的最大深度)

    [LeetCode] 104. Maximum Depth of Binary Tree 二叉树的最大深度 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no child

  • C++实现LeetCode(103.二叉树的之字形层序遍历)

    [LeetCode] 103. Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example

  • C++实现LeetCode(100.判断相同树)

    [LeetCode] 100. Same Tree 判断相同树 Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input:     1     

  • C++实现LeetCode(107.二叉树层序遍历之二)

    C++实现LeetCode(107.二叉树层序遍历之二)

    [LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二 Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root). Example 1: Input: root = [3

  • C++实现LeetCode(102.二叉树层序遍历)

    [LeetCode] 102. Binary Tree Level Order Traversal 二叉树层序遍历 Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree {3,9,20,#,#,15,7},     3 / \ 9  20 /  \ 15 

  • C++实现LeetCode(108.将有序数组转为二叉搜索树)

    [LeetCode] 108.Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树 Given an array 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 wh

  • C++实现LeetCode(109.将有序链表转为二叉搜索树)

    [LeetCode] 109.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. For this problem, a height-balanced binary tree is defined as a binary

  • 前端算法leetcode109题解有序链表转换二叉搜索树

    前端算法leetcode109题解有序链表转换二叉搜索树

    目录 题目 解题思路-基础 代码实现 解题思路-优化 代码实现 解题思路-进阶 代码实现 题目 题目地址 给定一个单链表的头节点  head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树. 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1. 示例 1: 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0,-3,9,-10,null,5],它表示所示的高度平衡的二叉搜索树.

  • C++实现LeetCode(173.二叉搜索树迭代器)

    [LeetCode] 173.Binary Search Tree Iterator 二叉搜索树迭代器 Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST. Note: next() and

  • C++实现LeetCode(98.验证二叉搜索树)

    [LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The ri

  • C++实现LeetCode(96.独一无二的二叉搜索树)

    [LeetCode] 96. Unique Binary Search Trees 独一无二的二叉搜索树 Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1         3  

  • C++实现LeetCode(95.独一无二的二叉搜索树之二)

    [LeetCode] 95. Unique Binary Search Trees II 独一无二的二叉搜索树之二 Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n. Example: Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3],

  • C++实现LeetCode(99.复原二叉搜索树)

    [LeetCode] 99. Recover Binary Search Tree 复原二叉搜索树 Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Example 1: Input: [1,3,null,null,2]    1 / 3 \ 2 Output: [3,1,null,null,2]    3 / 1

  • Java合并两个及以上有序链表的示例详解

    目录 题目一:合并两个有序链表 题目一思路 题目一完整代码 题目二:合并多个有序链表 题目二关键思路 题目二完整代码 题目一:合并两个有序链表 题目链接 题目一思路 设置两个指针,一个指针(t1)指向l1链表头,另外一个指针(t2)指向l2链表头. 首先判断l1和l2的第一个元素,谁小,谁就是最后要返回的链表的头节点,如果l1和l2的第一个元素相等,随便取哪个都可以. 这样,我们就设置好了要返回链表的头节点,假设头节点是head, 依次移动t1和t2指针,谁小,谁就接入进来.依次操作,直到两个链

  • C++实现LeetCode(23.合并k个有序链表)

    [LeetCode] 23. Merge k Sorted Lists 合并k个有序链表 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 这

随机推荐