leetcode算法【108】将有序数组转换为二叉搜索树

朴灿烈づ我的快乐病毒、 2022-11-26 06:58 55阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
    
    本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
    
    示例:
    
    给定有序数组: [-10,-3,0,5,9],
    
    一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
    
          0
         / \
       -3   9
       /   /
     -10  5

#### 方案： ####

*  二分法构造，算是前序遍历

package cmcandy.java_language_answers;
    
    /** * Created by CHEN on 2020/8/10. */
    public class _0108 { 
        /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
        static public class TreeNode { 
            int val;
            TreeNode left;
            TreeNode right;
    
            TreeNode(int x) { 
                val = x;
            }
    
            @Override
            public String toString() { 
                return "TreeNode{" +
                        "val=" + val +
                        ", left=" + left +
                        ", right=" + right +
                        '}';
            }
        }
    
        static class Solution { 
            private TreeNode root;
            private int[] nums;
    
            public TreeNode sortedArrayToBST(int[] nums) { 
                //二分法
                this.nums = nums;
                int length = nums.length;
                if (length == 0) return null;
                int left = 0;
                int right = length - 1;
                int mid = (right + left) / 2;
                root = new TreeNode(nums[mid]);
                //构建左右子树
                root.left = build(left, mid - 1, root.left);
                root.right = build(mid + 1, length - 1, root.right);
                return root;
            }
    
    
            public TreeNode build(int left, int right, TreeNode node) { 
    
                if (left > right) return null;
                int mid = (left + right) / 2;
                if (mid == left) { 
                    //说明这时候right=left+1
                    //或者说right==left
                    if (right == left) { 
                        node = new TreeNode(nums[mid]);
                        return node;
                    } else if (right == left + 1) { 
                        node = new TreeNode(nums[mid]);
                        node.right = new TreeNode(nums[mid + 1]);
                        return node;
                    }
                } else { 
                    //如果还比较多，那就继续
                    node = new TreeNode(nums[mid]);
                    node.left = build(left, mid - 1, node.left);
                    node.right = build(mid + 1, right, node.right);
                    return node;
                }
                return null;
            }
        }
    
        public static void main(String[] args) { 
            Solution solution = new Solution( );
            solution.sortedArrayToBST(new int[]{ 0}).toString( );
        }
    }

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode