108&109. 将有序数组（链表）转换为二叉搜索树

二叉搜索树（Binary Search Tree）具有以下性质：它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。
平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树，或者它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

108. 将有序数组转换为二叉搜索树

本题来自 LeetCode：108. 将有序数组转换为二叉搜索树^[1]

题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点   的左右两个子树的高度差的绝对值不超过 1。
示例:

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

      0
     / 
   -3   9
   /   /
 -10  5

题目分析

由于数组是升序的，故可以采用二分法来构建高度平衡的二叉搜索树。由于数组可以快速找到中心节点，故以中心节点为父节点，将数组分成两段，左边的数组对应左子树，右边的数组对应右子树。

题目解答

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null) {
            return null;
        }
        return buildBST(nums, 0, nums.length - 1);
    }

    public TreeNode buildBST(int[] nums, int left, int right) {
        if(left  right) {
            return null;
        }
        // 二分法保证是平衡二叉树
        int mid = left + (right - left) / 2;
        // 父节点
        TreeNode node = new TreeNode(nums[mid]);
        // 构建左子树
        node.left = buildBST(nums, left, mid - 1);
        // 构建右子树
        node.right = buildBST(nums, mid + 1, right);
        return node;
    }
}

复杂度分析：
时间复杂度： O(n)
空间复杂度： O(log(n))

109. 有序链表转换二叉搜索树

本题来自 LeetCode：109. 有序链表转换二叉搜索树^[2]

题目描述

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点   的左右两个子树的高度差的绝对值不超过 1。
示例:

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

题目分析

和题 108. 将有序数组转换为二叉搜索树不同的是，本题的源数据结构是链表，无法快速访问链表的中心节点，故需要通过快慢指针来找到中心节点，然后再采用二分法来解答。

题目解答

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) {
            return null;
        }
        if(head.next == null) {
            return new TreeNode(head.val);
        }
        ListNode slow = head;
        ListNode fast = head.next.next;
        //  将链表分成相等的两段，slow位于中心的前一个节点
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow.next为中心位置
        TreeNode treeNode = new TreeNode(slow.next.val);
        // 递归处理右子树
        treeNode.right = sortedListToBST(slow.next.next);
        // 将链表断开，防止重复处理
        slow.next = null;
        // 递归处理左子树
        treeNode.left = sortedListToBST(head);
        return treeNode;
    }
}

复杂度分析：
时间复杂度： O(nlog(n))
空间复杂度： O(log(n))

参考资料

108. 将有序数组转换为二叉搜索树: https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree

109. 有序链表转换二叉搜索树: https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree

原文始发于微信公众号（xiaogan的技术博客）：