【LeetCode】 37 将有序数组转换为二叉搜索树

题目

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

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

示例:

给定的有序链表: [-10, -3, 0, 5, 9],

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

      0
     / \
   -3   9
   /   /
 -10  5

思路

https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/jiang-you-xu-shu-zu-zhuan-huan-wei-er-cha-sou-s-15/

方法helper(left, right) 使用数组 nums 中索引从 leftright 的元素创建 BST:

  • 如果 left > right,子树中不存在元素,返回空。

  • 找出中间元素:p = (left + right) // 2

  • 创建根节点:root = TreeNode(nums[p])

  • 递归创建左子树 root.left = helper(left, p - 1) 和右子树 root.right = helper(p + 1, right)

  • 返回 helper(0, len(nums) - 1)

img

代码

class Solution {
  int[] nums;

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

    // 总是选择左中间节点作为根
    int p = (left + right) / 2;

    // 有序遍历:左->节点->右
    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);
  }
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×