乐趣区

关于java:LeetCode108将有序数组转换为二叉搜索树

将有序数组转换为二叉搜寻树

题目形容:给你一个整数数组 nums,其中元素曾经按 升序 排列,请你将其转换为一棵 高度均衡 二叉搜寻树。

高度均衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1」的二叉树。

示例阐明请见 LeetCode 官网。

起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。

解法一:递归

依据二叉搜寻树的性质,因为给定的数组是按升序排列的,所以能够确定数组 num 即为该二叉搜寻树的中序遍历序列,为了失去一颗均衡的二叉树,取数组两头地位的节点作为根节点,这样,左右子树的节点较为均衡,具体处理过程如下:

  • 调用递归办法,初始的起始地位为数组的长度;
  • 当终点地位大于起点地位时,阐明节点曾经遍历完了,间接返回空树;
  • 获取两头地位的值作为根节点,这样左右子树的节点树是比拟平衡的;
  • 而后递归取得以后根节点的左右子树;
  • 最初返回根节点即为均衡的二叉搜寻树。
import com.kaesar.leetcode.TreeNode;

public class LeetCode_108 {public static TreeNode sortedArrayToBST(int[] nums) {
        // 调用递归办法,初始的起始地位为数组的长度
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    /**
     * 递归
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */
    private static TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        // 当终点地位大于起点地位时,阐明节点曾经遍历完了,间接返回空树
        if (left > right) {return null;}
        // 获取两头地位的值作为根节点,这样左右子树的节点树是较为平衡点
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        // 而后递归取得以后根节点的左右子树
        root.left = sortedArrayToBST(nums, left, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, right);
        return root;
    }

    public static void main(String[] args) {int[] nums = new int[]{-10, -3, 0, 5, 9};
        sortedArrayToBST(nums).print();}
}

【每日寄语】 不辜负每个向阳,不旷废每个深夜,因平庸而奋斗,因奋斗而不平庸。

退出移动版