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

ゞ浴缸里的玫瑰 2023-10-05 21:22 16阅读 0赞

[108. 将有序数组转换为二叉搜索树][108.]

难度简单713

给你一个整数数组 nums ，其中元素已经按 **升序** 排列，请你将其转换为一棵 **高度平衡** 二叉搜索树。

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

**示例** **1****：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70][]

**输入：**nums = \[-10,-3,0,5,9\]

**输出：**\[0,-3,9,-10,null,5\]

**解释：**\[0,-10,5,null,-3,null,9\] 也将被视为正确答案：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70 1][]

**示例** **2****：**

![20210308134052895.jpeg][]

**输入：**nums = \[1,3\]

**输出：**\[3,1\]

**解释：**\[1,3\] 和 \[3,1\] 都是高度平衡二叉搜索树。

**提示：**

*  1 <= nums.length <= 104
 *  \-104 <= nums\[i\] <= 104
 *  nums 按 **严格递增** 顺序排列

package Solution108;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    class Solution {
    	public TreeNode sortedArrayToBST(int[] nums) {
    
    		int n = nums.length;
    		TreeNode root = sortedArrayToBST(nums, 0, n - 1);
    
    		return root;
    	}
    
    	TreeNode sortedArrayToBST(int arr[], int start, int end) {
    		// System.out.println(Arrays.toString(arr));
    
    		/* Base Case */
    		if (start > end) {
    			return null;
    		}
    
    		/* Get the middle element and make it root */
    		int mid = (start + end) / 2;
    		TreeNode node = new TreeNode(arr[mid]);
    
    		/*
    		 * Recursively construct the left subtree and make it left child of root
    		 */
    		node.left = sortedArrayToBST(arr, start, mid - 1);
    
    		/*
    		 * Recursively construct the right subtree and make it right child of root
    		 */
    		node.right = sortedArrayToBST(arr, mid + 1, end);
    
    		return node;
    	}
    
    	public List<List<Integer>> levelOrderBottom(TreeNode root) {
    		LinkedList<List<Integer>> result = new LinkedList<>();
    		if (root == null)
    			return result;
    		Queue<TreeNode> queue = new LinkedList<>();
    		queue.add(root);
    		while (!queue.isEmpty()) {
    			List<Integer> oneLevel = new ArrayList<>();
    			// 每次都取出一层的所有数据
    			int count = queue.size();
    			for (int i = 0; i < count; i++) {
    				TreeNode node = queue.poll();
    				oneLevel.add(node.val);
    				if (node.left != null)
    					queue.add(node.left);
    				if (node.right != null)
    					queue.add(node.right);
    			}
    			// 每次都往队头塞
    			result.addFirst(oneLevel);
    		}
    		return result;
    	}
    
    	public static List<List<Integer>> levelOrder(TreeNode root) {
    		if (root == null) {
    			return Collections.emptyList();
    		}
    		Queue<TreeNode> queue = new LinkedList<TreeNode>();
    		queue.add(root);
    		int count = 1;
    		List<List<Integer>> finalList = new ArrayList<List<Integer>>();
    		while (count != 0) {
    			List<Integer> list = new ArrayList<Integer>();
    			Queue<TreeNode> nextQueue = new LinkedList<TreeNode>();
    			while (!queue.isEmpty()) {
    				TreeNode node = queue.poll();
    				list.add(node.val);
    				count--;
    				if (node.left != null) {
    					nextQueue.add(node.left);
    				}
    				if (node.right != null) {
    					nextQueue.add(node.right);
    				}
    			}
    			finalList.add(list);
    			count = nextQueue.size();
    			queue = nextQueue;
    		}
    		return finalList;
    	}
    
    	public static void main(String[] args) {
    
    		Solution sol = new Solution();
    
    		int[] nums = { -10, -3, 0, 5, 9 };
    
    		System.out.println(levelOrder(sol.sortedArrayToBST(nums)));
    	}
    
    }

[108.]: https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210308134052881.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210308134052890.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI=,size_16,color_FFFFFF,t_70
[20210308134052895.jpeg]: https://img-blog.csdnimg.cn/20210308134052895.jpeg