LeetCode（Binary Search Tree)108. Convert Sorted Array to Binary Search Tree

左手的ㄟ右手 2023-09-26 20:39 103阅读 0赞

# 1.问题 #

Given an integer array nums where the elements are sorted in ascending order, convert it to a  
height-balanced  
binary search tree.

Example 1:

![在这里插入图片描述][a7fc36aa03a9464d8892888cea88577c.png]

> Input: nums = \[-10,-3,0,5,9\]  
> Output: \[0,-3,9,-10,null,5\]  
> Explanation: \[0,-10,5,null,-3,null,9\] is also accepted:

![在这里插入图片描述][fe03f684124c4090bf1c97d432a92abb.png]

Example 2:

![在这里插入图片描述][f9dbc30f4e394aefbd588328d998fab4.png]

> Input: nums = \[1,3\]  
> Output: \[3,1\]  
> Explanation: \[1,null,3\] and \[3,1\] are both height-balanced BSTs.

Constraints:

*  1 <= nums.length <= 104
 *  \-104 <= nums\[i\] <= 104
 *  nums is sorted in a strictly increasing order.

# 2. 解题思路 #

## 方法1： ##

> 利用二分法，每次选取有序数组的`中间元素作为根节点`，然后将`左半部分的数组构造成左子树`，将`右半部分的数组构造成右子树`。这样，得到的`二叉搜索树就是高度平衡的`。  
> 具体的实现过程可以使用递归函数来完成。递归函数 sortedArrayToBST 的参数包括有序数组 nums、数组的起始下标 start 和数组的终止下标 end。递归函数的实现过程如下：  
> 1.当 start > end 时，表示当前区间内已经没有元素了，递归结束，应该返回 null。  
> 2.计算当前区间内的中间元素下标 mid。  
> 3.以中间元素为根节点构造一个新的二叉搜索树节点 node。  
> 4.递归构造左子树，即调用 sortedArrayToBST(nums, start, mid - 1)。  
> 5.递归构造右子树，即调用 sortedArrayToBST(nums, mid + 1, end)。  
> 6.将左子树和右子树分别挂到根节点上，即 node.left = 左子树 和 node.right = 右子树。  
> 7.返回当前根节点 node。  
> 8.最终，调用 sortedArrayToBST(nums) 函数即可将有序数组 nums 转化为高度平衡的二叉搜索树。

## 方法2： ##

> 中序遍历的思路来解题  
> 首先，在二叉搜索树中，`中序遍历`是`按照节点值的大小顺序遍历的`，因此将有序数组按照中序遍历的顺序排列后，`数组中间的元素一定是根节点`，`左半部分的元素构造成左子树`，`右半部分的元素构造成右子树`。这样，就可以得到`一个高度平衡的二叉搜索树`。  
> 具体实现可以使用递归函数 buildBST 来完成，递归函数的参数包括有序数组 nums、数组的起始下标 start 和数组的终止下标 end。递归函数的实现过程如下：  
> 1.当 start > end 时，表示当前区间内已经没有元素了，递归结束，应该返回 null。  
> 2.计算当前区间内的中间元素下标 mid。  
> 3.以中间元素为根节点构造一个新的二叉搜索树节点 node。  
> 4.递归构造左子树，即调用 buildBST(nums, start, mid - 1)。  
> 5.将 node 挂到左子树上。  
> 6.递归构造右子树，即调用 buildBST(nums, mid + 1, end)。  
> 7.将 node 挂到右子树上。  
> 8.返回当前根节点 node。  
> 9.最终，调用 buildBST(nums) 函数即可将有序数组 nums 转化为高度平衡的二叉搜索树。

## 方法3： ##

> 使用迭代和队列的方法来避免使用递归的栈空间。  
> 1.首先，如果输入的有序数组是空数组，则直接返回空节点null。  
> 2.接着，根据数组长度n计算中间节点的索引mid，将该节点的值作为根节点的值，创建一个根节点root。  
> 3.然后，初始化一个队列q，将根节点和其左右子树的数组索引添加到队列中。  
> 4.接着，循环处理队列中的元素。在循环中，获取队列中的当前元素curr，它包含了父节点parent和它的左右子树的数组索引indices。  
> 5.如果左右索引没有越界，并且父节点parent不为空，则计算中间节点mid，创建一个新的节点child，根据child的值与父节点的值的大小关系，将child作为parent的左孩子或右孩子。  
> 6.最后，将child的左右子树的数组索引加入队列中，继续下一轮循环。当队列为空时，表示已经构建完整个平衡二叉搜索树，返回根节点root即可。  
> 7.总体来说，这个算法的时间复杂度是O(n)，其中n是数组长度，因为需要遍历整个数组并创建每个节点。空间复杂度是O(n)，因为需要使用一个队列来保存节点和它们的数组索引。

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public TreeNode sortedArrayToBST(int[] nums) {
        
            int start = 0;  // 数组的起始下标
            int end = nums.length - 1;  // 数组的终止下标
            return sortedArrayToBST(nums, start, end);  // 调用递归函数
        }
        
        public TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        
            if (start > end) {
          // 当 start > end 时，当前区间内已经没有元素，返回 null
                return null;
            }
            int mid = (start + end) / 2;  // 计算中间元素的下标
            TreeNode node = new TreeNode(nums[mid]);  // 构造以中间元素为根节点的二叉搜索树
            node.left = sortedArrayToBST(nums, start, mid - 1);  // 构造左子树
            node.right = sortedArrayToBST(nums, mid + 1, end);  // 构造右子树
            return node;  // 返回当前根节点
        }
    }

## 代码2： ##

class Solution {
        
        public TreeNode sortedArrayToBST(int[] nums) {
        
            // 判断输入数组是否为空
            if (nums == null || nums.length == 0) {
        
                return null;
            }
            // 构造二叉搜索树
            return buildBST(nums, 0, nums.length - 1);
        }
        
        private TreeNode buildBST(int[] nums, int start, int end) {
        
            // 如果起始下标大于终止下标，则当前区间内已经没有元素了，递归结束，返回 null
            if (start > end) {
        
                return null;
            }
            // 计算当前区间内的中间元素下标
            int mid = (start + end) / 2;
            // 以中间元素为根节点构造一个新的二叉搜索树节点
            TreeNode node = new TreeNode(nums[mid]);
            // 递归构造左子树
            node.left = buildBST(nums, start, mid - 1);
            // 递归构造右子树
            node.right = buildBST(nums, mid + 1, end);
            // 返回当前根节点
            return node;
        }
    }

## 代码3： ##

class Solution {
        
        public TreeNode sortedArrayToBST(int[] nums) {
        
          //如果数组为空则返回 null
            if (nums.length == 0) {
        
                return null;
            }
     
            int n = nums.length;
            int mid = n / 2;
            TreeNode root = new TreeNode(nums[mid]);
            // 初始化队列
            Queue<Object[]> q = new LinkedList<>();
            // push the root and its indices to the queue
            q.add(new Object[] {
         root,
                                 new int[] {
         0, mid - 1 } });
            q.add(new Object[] {
        
                root, new int[] {
         mid + 1, n - 1 } });
     
            while (!q.isEmpty()) {
        
                // 从队列中获取前面的元素
                Object[] curr = q.poll();
     
                // 获取父节点及其索引
                TreeNode parent = (TreeNode)curr[0];
                int[] indices = (int[])curr[1];
                int left = indices[0];
                int right = indices[1];
     
                // 如果有要处理的元素和父元素
                // 节点不为空
                if (left <= right && parent != null) {
        
                    mid = (left + right) / 2;
                    TreeNode child = new TreeNode(nums[mid]);
     
                    // 设置子节点为左孩子或右孩子
                    // 父节点的
                    if (nums[mid] < parent.val) {
        
                        parent.left = child;
                    }
                    else {
        
                        parent.right = child;
                    }
     
                    // 推动左右孩子和他们的
                    // 队列索引
                    q.add(new Object[] {
        
                        child, new int[] {
         left, mid - 1 } });
                    q.add(new Object[] {
        
                        child, new int[] {
         mid + 1, right } });
                }
            }
     
            return root;
        }
    }

[a7fc36aa03a9464d8892888cea88577c.png]: https://img-blog.csdnimg.cn/a7fc36aa03a9464d8892888cea88577c.png
[fe03f684124c4090bf1c97d432a92abb.png]: https://img-blog.csdnimg.cn/fe03f684124c4090bf1c97d432a92abb.png
[f9dbc30f4e394aefbd588328d998fab4.png]: https://img-blog.csdnimg.cn/f9dbc30f4e394aefbd588328d998fab4.png