专栏首页LeetCodeLeetCode <dfs>108&109. Array & List to Binary Search Tree
原创

LeetCode <dfs>108&109. Array & List to Binary Search Tree

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 which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-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

题目大意:把一个有序的数组转化为二分搜索树

解法:

思路:把中间的元素作为根节点,构造二分搜索树。

  public TreeNode sortedArrayToBST(int[] nums) {
        int length = nums.length;
        sortedArrayToBST_recursion(0,length-1,nums);
        return sortedArrayToBST_recursion(0,length-1,nums);
    }

    public TreeNode sortedArrayToBST_recursion(int start , int end ,int[] nums){
        if(start>end) return null;
        int mid = (end + start)/2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = sortedArrayToBST_recursion(start,mid-1,nums);
        node.right = sortedArrayToBST_recursion(mid+1,end,nums);
        return node;
    }

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

题目大意:把一个有序的链表转化为二分搜索树。

解法:

 public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
 
        while (fast!=null && fast.next !=null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

  
        if (pre!=null) pre.next =null;
        else head = null;
    
        TreeNode root = new TreeNode(slow.val);
        ListNode start = head;
        root.left = sortedListToBST(start);
        start = slow.next;
        root.right = sortedListToBST(start);
        return root;
    }

换一种写法:思路与上面同

     public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = new ListNode(0);
        pre.next = head;
        while (fast!=null && fast.next !=null){
            pre = pre.next;
            slow = slow.next;
            fast = fast.next.next;
        }

        if (pre.next == head) head =null;
        pre.next = null;
        TreeNode root = new TreeNode(slow.val);
        ListNode start = head;
        root.left = sortedListToBST(start);
        start = slow.next;
        root.right = sortedListToBST(start);
        return root;
    }

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode <Stack>84&85. Maximal Rectangle&Largest Rectangle in Histogram

    Given n non-negative integers representing the histogram's bar height where the ...

    大学里的混子
  • LeetCode SingleNumber I,II,III

    Given a non-empty array of integers, every element appears twice except for one....

    大学里的混子
  • LeetCode 169. Majority Element

    思路:数组中有一个数字的出现次数超过一半,也就是说这个数字的出现次数比其他的所有的数字的出现次数之和还要多。因此我们可以考虑遍历数组的时候保存两个值,一个是数组...

    大学里的混子
  • JavaUtil_03_图片处理工具类

    shirayner
  • HDOJ 1004

    Let the Balloon Rise Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 655...

    用户1154259
  • python: int函数

    JNingWei
  • 【图像处理100问】图像处理之各种像素操作效果(上)

    学校把很多考试都放在暑假考了,我们专业有6科,分布在一个月内。又要备赛数学建模,快乐暑假已经被榨干了... ...

    周旋
  • 1080 线段树练习

    1080 线段树练习 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description 一...

    attack
  • Leetcode: Binary Tree Right Side View

    Given a binary tree, imagine yourself standing on the right side of it, return t...

    卡尔曼和玻尔兹曼谁曼
  • linux系统编程之进程(三):exec系列函数和system函数

    一、exec替换进程映象 在进程的创建上Unix采用了一个独特的方法,它将进程创建与加载一个新进程映象分离。这样的好处是有更多的余地对两种操作进行管理。当我们创...

    s1mba

扫码关注云+社区

领取腾讯云代金券