我正在处理“将有序数组转换为具有最小高度的二叉搜索树”的问题,其要求如下:
给定一个已排序(按递增顺序)的数组,转换它以创建具有最小高度的二叉树。
我无法找到为什么我的递归不停止的原因。它应该在7被传递时停止,并且不会再次打印出7。我还发现了一个类似的答案,看起来使用了与我的相同策略,但它可以正常工作。(我不认为我的问题和上面列出的那些问题是重复的,但我仍然想感谢您为我提供链接。它们让我更好地解决了我的问题。)
以下是我的代码:
当我运行它时,出现了以下情况。
我的输入 [1,2,3,4,5,6,7,8]
我的输出 {4,2,6,1,3,5,7,#,#,#,#,#,#,7,8}
期望结果 {4,2,6,1,3,5,7,#,#,#,#,#,#,#,8}
为什么右侧有重复的7?由于7已经被使用,它应该被移除。
我发现我的想法与以下答案相似:
给定一个已排序(按递增顺序)的数组,转换它以创建具有最小高度的二叉树。
我无法找到为什么我的递归不停止的原因。它应该在7被传递时停止,并且不会再次打印出7。我还发现了一个类似的答案,看起来使用了与我的相同策略,但它可以正常工作。(我不认为我的问题和上面列出的那些问题是重复的,但我仍然想感谢您为我提供链接。它们让我更好地解决了我的问题。)
以下是我的代码:
public TreeNode sortedArrayToBST(int[] A) {
int len = A.length;
if(len <= 0){
return null;
}
TreeNode root = new TreeNode(A[(len - 1) / 2]);
if(len == 1){
return root;
}
else{
helper(root, A, 0, len - 1);
}
return root;
}
public void helper(TreeNode root, int[] A, int leftPoint, int rightPoint){
if((rightPoint - leftPoint) <= 0){
return;
}
int mid = (rightPoint - leftPoint) / 2 + leftPoint;
int leftChild = (mid - 1 - leftPoint) / 2 + leftPoint;
int rightChild = (rightPoint - (mid + 1)) / 2 + mid + 1;
TreeNode left = new TreeNode(A[leftChild]);
root.left = left;
TreeNode right = new TreeNode(A[rightChild]);
root.right = right;
helper(root.left, A, leftPoint, mid - 1);
helper(root.right, A, mid + 1, rightPoint);
return;
}
当我运行它时,出现了以下情况。
我的输入 [1,2,3,4,5,6,7,8]
我的输出 {4,2,6,1,3,5,7,#,#,#,#,#,#,7,8}
期望结果 {4,2,6,1,3,5,7,#,#,#,#,#,#,#,8}
为什么右侧有重复的7?由于7已经被使用,它应该被移除。
我发现我的想法与以下答案相似:
public TreeNode sortedArrayToBST(int[] A) {
// write your code here
int len = A.length;
if(len <= 0){
return null;
}
TreeNode root = helper1(A, 0, len - 1);
return root;
}
public TreeNode helper1(int[] A, int low, int high){
if(low > high){
return null;
}
int mid = (high + low) / 2;
TreeNode root = new TreeNode(A[mid]);
root.left = helper1(A, low, mid - 1);
root.right = helper1(A, mid + 1, high);
return root;
}