将排序后的数组转换为最小高度的二叉搜索树 [英] Convert sorted array to binary search tree with minimal height

问题描述

我想将排序后的整数数组转换为二进制搜索树.我已经在下面发布了我的代码.我无法想象的是，递归实际上是如何与for循环一起插入的.

I want to convert a sorted integer array into a binary search tree. I have posted my code below. What I cannot picture is how the recursion actually works with the for loop as inserting.

因此，如果我的数组是[1,3,4,5,8,10]，我将数组的中间设为4，成为BST的根，然后从数组的开头循环并插入到刚创建的带有根的树.我的问题是为什么插入结果的顺序不像给定的数组那样?

So if my array is [1,3,4, 5,8,10] I make 4, which is the mid of the array, become the root of my BST, then loop from the start of array and insert to the tree with root just created. My question is why the order of result inserted is not as the sorted given array?

public TreeNode sortedArrayToBST(int[] A) {  
    if (A == null || A.length == 0){
       return null;
    }
    TreeNode root = new TreeNode(findMid(A));
    for (int i = 0; i < A.length; ++i){
        insert(root, A[i]);
    }      
 return root;
}




private int findMid(int[] A){

    int left = 0;
    int right = A.length -1;
    int mid = A[left + (right - left)/2];
    return mid;
}

private void insert (TreeNode root, int val){

    if (root == null || root.val == val){
        return;
    }
    if (val < root.val){
            TreeNode left = new TreeNode(val);
            root.left = left;
        }
    if (val > root.val){
            TreeNode right = new TreeNode(val);
            root.right = right;
        }

    insert(root.left,val);
    insert(root.right,val);

}

推荐答案

您的递归insert方法有几个问题.首先，每次val不等于根的值，就创建一个新节点.这是有问题的，因为这样做会创建多个节点，并在递归的每个步骤中将根节点的子节点设置为这些新节点，这是多余的.让我们遍历每个节点的方法.

You have a couple problems with your recursive insert method. First off, everytime the val is not equal to the root's value, you create a new node. This is faulty because by doing this, you create multiple nodes and set the root's child at each step of the recursion to these new nodes, which is redundant. Let's go through your method for each node.

添加4

   4

添加1

   4
  / 
 1

添加3

   4
  /
 3

在这一点上，我们可以查明错误.为什么将4的左孩子替换为3?让我们来看一下insert方法，其中root是值为4的节点，而val为3的节点.

At this point, we can pinpoint the error. Why was 4's left child replaced with 3? Let's go through your insert method where root is the node with value 4 and val is 3.

• 第一个if陈述条件的计算结果为false，因此继续
• 第二个if语句条件的值为true，因此用val创建一个新节点，并将root.left设置为等于该新节点
• 第三种if陈述条件的计算结果为false，请继续
• 递归调用insert(3.left, 3)自3 == 3
开始返回
• 递归调用insert(null, 3)自root == null
开始返回

• First if-statement condition evaluates to false, so move on
• Second if-statement condition evaluates to true, so create a new node with val and set root.left equal to this new node
• Third if-statement condition evaluates to false, so move on
• Recursive call insert(3.left, 3) just returns since 3 == 3
• Recursive call insert(null, 3) just returns since root == null

那么解决方法是什么? 停止在调用堆栈中的每个递归调用处创建新节点.信不信由你，您仅应在root为null时创建一个新节点，因为这表明您已将树遍历到一个空孩子.递归调用呢?无需对根节点的每个子节点进行递归调用，因为您只需沿BST中的一个遍历路径前进.您可以在每个节点处向左或向右转.因此，您要做的只是根据相对于根值的val值进行递归调用.这就是它的样子，

So what's the fix? STOP creating new nodes at every recursive call in the call stack. Believe it or not, you should only be creating a new node when root is null, because this signifies that you've traversed the tree down to an empty child. What about the recursive calls? There's no need to do a recursive call on each of the root's children because you only go down one traversal path in a BST. You either turn left or right at each node. So what you do is only make a recursive call depending on the value of val relative to the root's value. Here's what it should look like,

private TreeNode insert (TreeNode root, int val){

    if (root == null){
        return new TreeNode(val);
    }
    if (val == root.val){
        //if you don't want to add repeats in the tree, then
        //add your own code to deal with that here
        //although as it stands now, this code will not add repeats
    }
    if (val < root.val){
            root.left = insert(root.left, val);
    }
    if (val > root.val){
            root.right = insert(root.right, val);
    }
    return root;
}

这篇关于将排序后的数组转换为最小高度的二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！