1. 首页
  2. Leetcode经典148题

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

题目描述(中等难度)

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

“>108 题 吧,算法的关键是取到中间的数据做为根节点。而这里链表的话,由于不支持随机访问,所以会麻烦些。最简单的思路就是我们把链表先用线性表存起来,然后题目就转换成 108 题了。

为了方便,把上一道题的数组参数改为List

public TreeNode sortedListToBST(ListNode head) {
    ArrayList<Integer> nums = new ArrayList<>();
    while (head != null) {
        nums.add(head.val);
        head = head.next;
    }
    return sortedArrayToBST(nums);
}

public TreeNode sortedArrayToBST(ArrayList<Integer> nums) {
    return sortedArrayToBST(nums, 0, nums.size());
}

private TreeNode sortedArrayToBST(ArrayList<Integer> nums, int start, int end) {
    if (start == end) {
        return null;
    }
    int mid = (start + end) >>> 1;
    TreeNode root = new TreeNode(nums.get(mid));
    root.left = sortedArrayToBST(nums, start, mid);
    root.right = sortedArrayToBST(nums, mid + 1, end);
    return root;
}

时间复杂度:O(log(n))

空间复杂度:数组进行辅助,O(n)

解法二

参考 “>108 题 是一样的。

public TreeNode sortedListToBST(ListNode head) {
    return sortedArrayToBST(head, null);
}

private TreeNode sortedArrayToBST(ListNode head, ListNode tail) {
    if (head == tail) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != tail && fast.next != tail) {
        slow = slow.next;
        fast = fast.next.next;
    }

    TreeNode root = new TreeNode(slow.val);
    root.left = sortedArrayToBST(head, slow);
    root.right = sortedArrayToBST(slow.next, tail); 
    return root;
}

时间复杂度:根据递归式可知,T(n) = 2 * T(n / 2 ) + nO(nlog(n))

空间复杂度:O(log(n))

解法三

解法二虽然没有借助数组,优化了空间复杂度,但是时间复杂度增加了,那么有没有一种两全其美的方法,时间复杂度是解法一,空间复杂度是解法二。还真有,参考 public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); getAns(root, ans); return ans; } private void getAns(TreeNode node, List<Integer> ans) { if (node == null) { return; } getAns(node.left, ans); ans.add(node.val); getAns(node.right, ans); }

之前是将 node.val 进行保存,这里的话我们是给当前节点进行赋值,为了依次赋值,我们需要一个cur指针指向给定的数列,每赋一个值就进行后移。

ListNode cur = null;

public TreeNode sortedListToBST(ListNode head) {
    cur = head;
    int end = 0;
    while (head != null) {
        end++;
        head = head.next;
    }
    return sortedArrayToBSTHelper(0, end);
}

private TreeNode sortedArrayToBSTHelper(int start, int end) {
    if (start == end) {
        return null;
    }
    int mid = (start + end) >>> 1;
    //遍历左子树并且将根节点返回
    TreeNode left = sortedArrayToBSTHelper(start, mid);
    //遍历当前根节点并进行赋值
    TreeNode root = new TreeNode(cur.val);
    root.left = left;
    cur = cur.next; //指针后移,进行下一次的赋值
    //遍历右子树并且将根节点返回
    TreeNode right = sortedArrayToBSTHelper(mid + 1, end);
    root.right = right;
    return root;
}

时间复杂度:O(n),主要是得到开始的 end,需要遍历一遍链表。

空间复杂度:O(log(n)),递归压栈的消耗。

快慢指针求链表的中间值,这个技巧不错。此外,解法三的模仿中序遍历的过程,然后把给定的数组依次赋值过去,太强了。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetcode-109-Convert-Sorted-List-to-Binary-Search-Tree

链接:https://www.javajike.com/article/3246.html

« leetcode-108-Convert-Sorted-Array-to-Binary-Search-Tree
leetcode-110-Balanced-Binary-Tree»

相关推荐

QR code