力扣hot100 将有序数组转换为二叉搜索树 递归

2024-01-08 13:03:54

👨?🏫 题目地址
在这里插入图片描述

  • 时间复杂度: O ( n ) O(n) O(n)

😋 AC code

/**
 * 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)
	{
		int n = nums.length;
		TreeNode ans = dfs(nums, 0, n - 1);
		return ans;
	}

	private TreeNode dfs(int[] nums, int l, int r)
	{
		if(l > r)//区间为空,返回 null
			return null;
		int m = l + r >> 1;//每次都取中间的点作为当前树的根结点
		TreeNode ans = new TreeNode(nums[m]);
		ans.left = dfs(nums, l, m - 1);
		ans.right = dfs(nums, m + 1, r);
		return ans;
	}
}

文章来源:https://blog.csdn.net/lt6666678/article/details/135378370
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。