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

Leecode-108-Convert Sorted Array to Binary Search Tree

题目描述

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

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

给定有序数组: [-10,-3,0,5,9],

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

      0
     / \
   -3   9
   /   /
 -10  5

Solution：DFS

• 深度优先遍历（DFS）
  • 这种方法以深度depth 为优先策略，从根节点开始一直遍历到某个叶子节点，回到根节点，再遍历另外一个分支。
  • 根据根节点，左孩子和右孩子的访问顺序又可以把DFS细分为 前序遍历，中序遍历，后序遍历。
• 这里有很重要的一点：有序数组转换成二叉搜索树的结果不唯一
  • 众所周知，二叉搜索树的中序遍历是一个升序序列。
  • 将有序数组作为输入，可以把该问题看作根据中序遍历创建二叉搜索树
  • 中序遍历不能唯一确定一棵二叉搜索树。
  • 先序和后序遍历不能确定一颗唯一的二叉搜索树
  • 中序+后序，后序+先序可以唯一确定一颗二叉搜索树
  • 因此，“有序数组 -> BST”有多种答案。

方法一：中序遍历（始终选择中间左边元素作为根节点）

• 方法helper(left,right,nums) 使用数组nums 中索引从left到right创建BST
  • 如果 left > right ，子树中不存在元素，返回空
  • 找出中间元素 p = (left + right) >>>1;
  • 创建根节点 root = TreeNode(nums[p])
  • 递归创建左子树 root.left = helper(left,p-1,nums)
  • 递归创建右子树 root.right = helper(p + 1,right)

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(0,nums.length - 1,nums);
    }

    private TreeNode helper (int left, int right , int[] nums) {
        // 退出递归的条件
        if (left > right){
            return null;
        }

        // 拿到中间节点作为根节点 （左侧）
        int p = (left + right) >>> 1;

        // inorder traversal: left -> node -> right
        TreeNode root = new TreeNode(nums[p]);
        root.left  = helper(left, p -1,nums);
        root.right = helper(p + 1,right,nums);

        return root;
    }
}

• 时间复杂度：O(N) 每个元素只访问一次
• 空间复杂度：O(N) 二叉搜索树空间O(N)，递归栈深度 O(logN)。

方法二：中序遍历：始终选择中间位置右边元素作为根节点

• 道理同上一个解法，这里不再重述

class Solution {
  int[] nums;

  public TreeNode helper(int left, int right) {
    if (left > right) return null;

    // always choose right middle node as a root
    int p = (left + right) / 2;
    if ((left + right) % 2 == 1) ++p;

    // inorder traversal: left -> node -> right
    TreeNode root = new TreeNode(nums[p]);
    root.left = helper(left, p - 1);
    root.right = helper(p + 1, right);
    return root;
  }

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

复杂度分析

• 时间复杂度：O(N)，每个元素只访问一次。

• 空间复杂度：O(N)，二叉搜索树空间O(N)，递归栈深度 O(logN)。

打赏