Merge pull request youngyangyang04#457 from daniel1n/patch-3

Update 0108.将有序数组转换为二叉搜索树.md
TwStarLord · Jul 4, 2021 · af3c7af · af3c7af
2 parents e2d8c0a + 4d64b1f
commit af3c7af
Showing 1 changed file with 71 additions and 0 deletions.
diff --git a/problems/0108.将有序数组转换为二叉搜索树.md b/problems/0108.将有序数组转换为二叉搜索树.md
@@ -209,6 +209,8 @@ public:
 
 
 Java：
+
+递归: 左闭右开 [left,right)
 ```Java
 class Solution {
     public TreeNode sortedArrayToBST(int[] nums) {
@@ -232,6 +234,75 @@ class Solution {
 
 ```
 
+递归: 左闭右闭 [left,right]
+```java
+class Solution {
+	public TreeNode sortedArrayToBST(int[] nums) {
+		TreeNode root = traversal(nums, 0, nums.length - 1);
+		return root;
+	}
+
+	// 左闭右闭区间[left, right)
+	private TreeNode traversal(int[] nums, int left, int right) {
+		if (left > right) return null;
+
+		int mid = left + ((right - left) >> 1);
+		TreeNode root = new TreeNode(nums[mid]);
+		root.left = traversal(nums, left, mid - 1);
+		root.right = traversal(nums, mid + 1, right);
+		return root;
+	}
+}
+```
+迭代: 左闭右闭 [left,right]
+```java
+class Solution {
+	public TreeNode sortedArrayToBST(int[] nums) {
+		if (nums.length == 0) return null;
+
+		//根节点初始化
+		TreeNode root = new TreeNode(-1);
+		Queue<TreeNode> nodeQueue = new LinkedList<>();
+		Queue<Integer> leftQueue = new LinkedList<>();
+		Queue<Integer> rightQueue = new LinkedList<>();
+
+		// 根节点入队列
+		nodeQueue.offer(root);
+		// 0为左区间下表初始位置
+		leftQueue.offer(0);
+		// nums.size() - 1为右区间下表初始位置
+		rightQueue.offer(nums.length - 1);
+
+		while (!nodeQueue.isEmpty()) {
+			TreeNode currNode = nodeQueue.poll();
+			int left = leftQueue.poll();
+			int right = rightQueue.poll();
+			int mid = left + ((right - left) >> 1);
+
+			// 将mid对应的元素给中间节点
+			currNode.val = nums[mid];
+
+			// 处理左区间
+			if (left <= mid - 1) {
+				currNode.left = new TreeNode(-1);
+				nodeQueue.offer(currNode.left);
+				leftQueue.offer(left);
+				rightQueue.offer(mid - 1);
+			}
+
+			// 处理右区间
+			if (right >= mid + 1) {
+				currNode.right = new TreeNode(-1);
+				nodeQueue.offer(currNode.right);
+				leftQueue.offer(mid + 1);
+				rightQueue.offer(right);
+			}
+		}
+		return root;
+	}
+}
+```
+
 Python：
 ```python3
 # Definition for a binary tree node.