将有序数组转换为二叉搜索树.力扣108

落日映苍穹つ 2023-10-01 21:03 4阅读 0赞

## 一、题目描述 ##

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16][]

## 二、思路 ##

由题目可知给出的数组是二叉树的中序遍历（根左右），所以数组中间的数是二叉树的根节点，从这个点出发，每次选择数组最中间的数作为根节点进行构建,假如给定数组是\[,-3-2,-1,0,1,2,3\]，下面进行图解

1.将数组的中间数字0作为根节点，数组被分成了两部分

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

2.继续递归调用此方法,-2和2分别构建成了左孩子和右孩子的根节点，同样孩子节点也被分成了两部分

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_18_color_FFFFFF_t_70_g_se_x_16][]

3.继续递归

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

三、代码实现

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            return helper(nums,0,nums.length - 1);
        }
        public TreeNode helper(int[] nums,int left,int right){
            if(left > right){
                return null;
            }
            int mid = (left + right)/2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = helper(nums,left,mid - 1);
            root.right = helper(nums,mid + 1,right);
            return root;
        } 
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/8c6bf3fe470a4f66807a0ad18be68314.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/aef61ec94f6f4de9b521f5ea1df389fc.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_18_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/171b7736e58849479706cfb28d49706c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_18,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/20db12b68d28458d8bc1cf38b277d9ee.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16