描述

题目描述

给出一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.

示例
输入：[-1,0,1,2]
返回值：{1,0,2,-1}

知识点：二叉搜索树，排序，数组，二分查找
难度：⭐⭐

题解

解题思路

对于有序数组，首先应该想到用二分法，接着是构造二叉搜索树的过程，应该想到用分治法，分别对左右子树进行构建后，再合并，而这个类似先构造左子树再构造右子树的过程，可以通过递归解决

方法一：递归+二分查找

图解

image-20210714225938267

算法流程：
  • 定义递归函数功能：找出数组num的[left,right]区间的中间偏大的元素
  • 二分法：因为递归是先找出并设置左子结点，因此mid要取的中间元素的偏大的中间元素
  • 向左递归，继续寻找左区间的根节点
  • 向右递归，继续寻找右区间的根节点
Java 版本代码如下：
import java.util.*;

public class Solution {
    public TreeNode sortedArrayToBST (int[] num) {
        if(num == null || num.length == 0) {
            return null;
        }
        return recur(num, 0, num.length - 1);
    }

    // 定义递归函数功能：找出数组num的[left,right]区间的中间偏大的元素
    private TreeNode recur(int[] num, int left, int right) {
        // 递归终止条件
        if(left > right) {
            return null;
        }
        // 因为递归是先找出并设置左子结点，因此mid要取的中间元素的偏大的中间元素
        // 例如[-1,0,1,2]，如果没有+1，则根节点会是中甲元素偏小的0，最后最大值2将是左子节点，不满足二叉搜索树特性
        int mid = left + ((right - left + 1) >> 1);
        TreeNode root = new TreeNode(num[mid]);
        // 向左递归，继续寻找左区间的根节点
        root.left =  recur(num, left, mid - 1);
        // 向右递归，继续寻找右区间的根节点
        root.right = recur(num, mid + 1, right);
        return root;
    }

}
Python 版本代码如下：
class Solution:
    def sortedArrayToBST(self , num ):
        if len(num) == 0:
            return None
        if len(num) == 1:
            return TreeNode(num[0])
        # 中间元素为当前区间的根节点
        idx = len(num) // 2
        node = TreeNode(num[idx])
        # 左右区间递归，寻找左右区间的根节点
        node.left = self.sortedArrayToBST(num[:idx])
        node.right = self.sortedArrayToBST(num[idx+1:])
        return node
复杂度分析：

时间复杂度 O(N)：尽管采用了二分法，但递归构造树时，递归经过每个结点，N为数组长度，及二叉搜索树结点个数
空间复杂度 O(N)：结果集用到了TreeNode保存最终结果，N为节点数

总结：遇到有序数组，一定要最先想到二分法，还能降低复杂度

方法二：迭代

算法流程：
  • 维护两个stack，一个保存结果，一个保存每次迭代的左右分界点
  • 迭代每个数组每个元素，先获取当前区间，以及当前区间根节点在数组的位置
  • 构造当前结点，接着根据左右区间，分别构建左右子节点
  • 每次都要更新保存左右分界点的stack
Java 版本代码如下：
import java.util.*;

public class Solution {
    public TreeNode sortedArrayToBST (int[] num) {
        if(num == null || num.length == 0) {
            return null;
        }
        // 保存结果
        Stack<TreeNode> res = new Stack<>();
        // 保存左右分界点
        Stack<Integer> stack = new Stack<>();
        // 初始化根节点
        TreeNode root = new TreeNode(0);
        res.push(root);
        stack.push(0);
        stack.push(num.length - 1);
        while(res.size() > 0) {
            // 获取当前区间
            int right = stack.pop();
            int left = stack.pop();
            // 当前区间根节点在数组的位置
            int mid = left + ((right - left + 1) >> 1);
            TreeNode node = res.pop();
            // 当前区间的根节点赋值
            node.val = num[mid];
            // 左区间，构建左子节点
            if(left <= mid - 1) {
                node.left = new TreeNode(0);
                // 初始化左子节点，为了下次构建二叉树
                res.push(node.left);
                stack.push(left);
                // 缩小为左区间
                stack.push(mid - 1);
            } 
            // 右区间，构建右子节点
            if(right >= mid + 1) {
                node.right = new TreeNode(0);
                res.push(node.right);
                stack.push(mid + 1);
                stack.push(right);
            }
        }
        return root;
    }
}
复杂度分析：

时间复杂度 O(N)：需要遍历N个结点
空间复杂度 O(logN)：栈所需的额外空间