LeetCode

LeetCode-108-数组转AVL

平衡二叉树

Posted by 刘知安 on 2019-12-01
文章目录
  1. LeetCode-108-数组转AVL
    1. 1. 题目描述
    2. 2. 思路
    3. 3. 代码
    4. 4. 相似题

LeetCode-108-数组转AVL

1. 题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

1
2
3
4
5
6
7
8
9
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

2. 思路

可以很明显的知道，一棵AVL的中序遍历就是原排序数组了，所以这个题相当于就是中序遍历的逆过程，类似二分查找，然后递归的构造二叉树即可，这个题也是easy题，不过还是想记录一下，因为之前刷的题基本都是数组/链表之类的，涉及到树的比较少，最近有时间我也会复习一下AVL相关的内容，并整理出一篇博客出来，敬请期待…

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * @ClassName SortedArr2AVL
 * @Deacription // TODO
 * @Author LiuZhian
 * @Date 2019-12-01 13:51
 * @Version 1.0
 **/

public class SortedArr2AVL {
    public TreeNode sortedArrayToBST(int[] nums) {

        int len = nums.length;
        if (len == 0)
            return null;
        int left = 0, right = len - 1;
        return buildTreeRecursive(nums, left, right);

    }

    public TreeNode buildTreeRecursive(int[] nums, int left, int right) {
        // 思路是类似二分查找，因为数组有序，中间的结点作为根节点
        // 左边的结点为左子树，右边结点为右子树，递归处理
        if (left == right)
            return new TreeNode(nums[left]);
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);

        TreeNode leftSubTree = (mid == left ? null : buildTreeRecursive(nums, left, mid - 1));
        TreeNode righttSubTree = (mid == right ? null : buildTreeRecursive(nums, mid + 1, right));
        root.left = leftSubTree;
        root.right = righttSubTree;

        return root;
    }

    public static void main(String[] args) {
        int[] nums = {-15,-10, -3, 0, 5, 9};
        SortedArr2AVL s = new SortedArr2AVL();
        TreeNode res = s.sortedArrayToBST(nums);
        System.out.println(res);
    }
}


// 平衡二叉树结点
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

4. 相似题

  • 109.有序链表转平衡二叉树
    这个题和108题其他条件一模一样，区别就是数组换成了链表，大致有两种解法：
  1. 用快慢指针不断找到链表的中间结点，然后再在左边和右边各自递归处理。时间复杂度为O(N*logN),空间复杂度为O(logN)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    public TreeNode sortedListToBST(ListNode head) {
        // 空链表
        if (head == null)
            return null;
        // 只有一个元素
        if (head.next == null)
            return new TreeNode(head.val);

        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = head;

        // slow指向中间结点，fast指向最后一个结点
        while (fast!=null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 让prev指针指向slow的前一个
        while (prev.next != slow) {
            prev = prev.next;
        }
        // 让原链表断成3部分，中间那个作为根节点
        TreeNode mid = new TreeNode(slow.val);
        prev.next = null;
        ListNode rightList = slow.next;
        mid.left = sortedListToBST(head);
        mid.right = sortedListToBST(rightList);

        return mid;
    }
  2. 先将链表中的所有元素记录用一个数组保存起来（这是为了到时候找中间结点是不要每次都去扫描链表），一种空间换时间的方式。
    时间复杂度为O(N),空间复杂度为O(N)
FEATURED TAGS
LeetCode
FRIENDS