[Leetcode] Convert Sorted Array/List to Binary Sea

wpw 发布于2019-08-14 12:40 / 667人阅读

摘要：我们可以用和两个值来限定子树在链表中的位置，通过递归的方式，深入找到最左边，然后开始顺序遍历链表链表当前节点作为全局变量，这样无论递归在哪我们都能拿到，同时建树。代码先递归的计算左子树创造根节点最后递归的计算右子树

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.

递归法 复杂度

时间 O(N) 空间 O(H)

思路

首先先分析下题目，二叉搜索树，有序链表，之间有什么关系？我们知道二叉搜索树做深度优先搜索就可以从小到大顺序读取树中节点，但是如何从一串有序的数字还原二叉搜索树呢？仔细观察的话可以发现，该串数字的中点应该就是整棵树的根，然后该根节点的左子树的根节点，又是左半边的中点，该根节点的右子树的根节点，又是右半边的中点，以此往复，链表第一个节点，就是最左边左“子树”的根节点（实际上已经是叶子节点了，但先看成只有一个节点的子树，最左边左子树的左节点和右节点都是空）。我们可以用start和end两个值来限定子树在链表中的位置，通过递归的方式，深入找到最左边，然后开始顺序遍历链表（链表当前节点作为全局变量，这样无论递归在哪我们都能拿到），同时建树。

代码

public class Solution {
    
    ListNode curr;
    
    public TreeNode sortedListToBST(ListNode head) {
        curr = head;
        int len = 0;
        // 先计算出链表的长度
        while(head != null){
            head = head.next;
            len++;
        }
        curr = head;
        // 开始建树
        return buildTree(0, len - 1);
    }
    
    private TreeNode buildTree(int start, int end){
        // 如果start>end，说明子树已经小到没有节点了，直接返回null
        if(start > end){
            return null;
        }
        // 找到中点
        int mid = start + (end - start) / 2;
        // 先递归的计算左子树
        TreeNode left = buildTree(start, mid - 1);
        // 然后建立根节点
        TreeNode root = new TreeNode(curr.val);
        // 链表顺序遍历
        curr = curr.next;
        // 最后计算右子树
        TreeNode right = buildTree(mid + 1, end);
        // 将三个节点连接起来
        root.left = left;
        root.right = right;
        return root;
    }
}

2018/10

var curr *ListNode

func buildTree(start int, end int) *TreeNode {
    if start > end {
        return nil
    }
    mid := start + (end-start)/2
    root := &TreeNode{}
    root.Left = buildTree(start, mid-1)
    root.Val = curr.Val
    curr = curr.Next
    root.Right = buildTree(mid+1, end)
    return root
}

func sortedListToBST(head *ListNode) *TreeNode {
    length := 0
    curr = head
    for curr != nil {
        curr = curr.Next
        length++
    }
    curr = head
    return buildTree(0, length-1)
}

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

递归法 复杂度

时间 O(N) 空间 O(H)

思路

和用链表建树的思路相似，实现更加简单，因为数组支持随机查询，我们可以直接访问中点而无须遍历链表。

代码

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildTree(nums, 0, nums.length - 1);
    }
    
    private TreeNode buildTree(int[] nums, int start, int end){
        if(start > end){
            return null;
        }
        int mid = start + (end - start) / 2;
        // 先递归的计算左子树
        TreeNode left = buildTree(nums, start, mid - 1);
        // 创造根节点
        TreeNode root = new TreeNode(nums[mid]);
        // 最后递归的计算右子树
        TreeNode right = buildTree(nums, mid + 1, end);
        root.left = left;
        root.right = right;
        return root;
    }
}

云服务器 GPU云服务器 sea Sorted LeetCode convert

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64624.html

[Leetcode-Tree] Convert Sorted Array to Binary Sea

摘要：解题思路平衡二叉树，其实就是数组中间的数作为根，利用递归实现左子树和右子树的构造。 Convert Sorted Array to Binary Search TreeGiven an array where elements are sorted in ascending order, convert it to a height balanced BST. 1.解题思路平衡二叉树，...

songze 2019-08-16 10:26 评论0 收藏0
[LeetCode] 108. Convert Sorted Array to Binary Sea

摘要：二分法找到数组的中位数，置为树的，递归找到前半段和后半段的中位数，分别置为左右子树。 Problem Given a sorted (increasing order) array, Convert it to create a binary tree with minimal height. Example Given [1,2,3,4,5,6,7], return 4 ...

SKYZACK 2019-08-14 15:17 评论0 收藏0
[LeetCode] Convert Sorted Array to Binary Search T

摘要：思路根据的性质，问题转化为找一个里的中位数，用一个函数，一路找中点，再通过前序遍历的方法把起来代码 Convert Sorted Array to Binary Search Tree With Minimal Height Given a sorted (increasing order) array, Convert it to create a binarytree with m...

willin 2019-08-16 10:33 评论0 收藏0
[LeetCode] 109. Convert Sorted List to Binary Sear

Problem 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 whi...

dongfangyiyu 2019-08-16 13:42 评论0 收藏0
leetcode109. Convert Sorted List to Binary Search

摘要：题目要求给一个按照递增顺序排列的链表。将该链表转化为平衡二叉树。思路和代码在这里需要注意的是，因为提供的数据结构为链表，所以我们必须顺序遍历才能知道该链表的长度以及该链表的中间位置。并依次递归左子节点和右子节点。题目要求 Given a singly linked list where elements are sorted in ascending order, convert i...

高胜山 2019-08-15 11:08 评论0 收藏0