[LC] 108题 将有序数组转换为二叉搜索树 (建树)

①题目

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

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

示例:

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

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

[LC] 108题 将有序数组转换为二叉搜索树 (建树)

 

 

②思路

   我没有好的思路,所以看得别人的答案,来源:https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-24/

   1、二叉搜索树的中序遍历刚好可以输出一个升序数组

   2、根据中序遍历还原一颗树,又想到了 105 题 和 106 题,通过中序遍历加前序遍历或者中序遍历加后序遍历来还原一棵树。前序(后序)遍历的作用呢?提供根节点!然后根据根节点,就可以递归的生成

        左右子树。

       这里的话,只有1个有序数组,没有前序或者后序遍历,怎么知道根节点呢?平衡二叉树,既然要做到平衡,我们只要把根节点选为数组的中点即可。

③代码

 1 class Solution {
 2     public TreeNode sortedArrayToBST(int[] nums) {
 3          return sortedArrayToBST(nums, 0, nums.length);
 4     }
 5 
 6     private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
 7         if (start == end) {
 8             return null;
 9         }
10         int mid = (start + end) >>> 1;    //无符号右移一位,其实就是/2
11         TreeNode root = new TreeNode(nums[mid]);    //把数组的中点的元素当做root
12         root.left = sortedArrayToBST(nums, start, mid);   //把当前左半边这一段的中点当做root.left
13         root.right = sortedArrayToBST(nums, mid + 1, end);    //把当前右半边这一段的中点当做root.right
14         return root;
15         }
16 }

 

④学到的东西

    1、第6行新增了个函数,第3行调用了该函数,该函数增加了输入参数的个数到3个,系统原来的函数只有1个输入参数。

    2、>>>是无符号右移,而>>>1  就是除以2的意思,即/2。

    3、如何新建1个结点,如11行所示,比如你想把3这个数当做一个根节点,那么就写TreeNode root = new TreeNode(3)就行了。

    4、感觉12-13行就是二分法的一种用法,注意退出条件是第7行。

上一篇:❤️543❤️带新手一起刷力扣 (LeetCode)❤️代码有详细的注释❤️反思总结❤️543. 二叉树的直径


下一篇:Leetcode 树-543-二叉树的直径