java - 二叉搜索树 - 插入

Question

You are given a pointer to the root of a binary search tree and a value to be inserted into the tree. Insert this value into its appropriate position in the binary search tree and return the root of the updated binary tree. You just have to complete the function.

我已经提供了我的代码，但有一个测试用例无法正常工作。这是我的代码:

static Node Insert(Node root,int value){
    Node d =root;
    Node q = new Node();
    q.left = null;
    q.right=null;
    q.data = value;
    while(true){
        if(value<d.data){
            if(d.left==null){d.left = q;
                           return root; }
            else{
                d= d.left ;
            }
        }
        else{
            if(value>d.data){
                if(d.right==null){d.right=q;
                                 return root;}
                else d = d.right;
            }
        }
    }
}

Answer 1

您遗漏了两种情况:value == d.data 和空树。

value == d.data:在那种情况下，树不会以任何方式改变，但您的代码不会中断并以无限循环结束。

最简单的解决方案是将这些行插入到 while 循环中:

if(value == d.data)
    return root;

树为空的情况是特定于实现的，因此很难针对这种情况提出任何解决方案。