java - 这两种对BST插入操作的实现有什么区别？

Question

有代码:

public class BST {
    public Node root;

    private class Node {
        int key;
        String value;
        int N;
        Node left, right;

        public Node(int k, String v, int n) {
            key = k;
            value = v;
            N = n;
        }
    }

    public String get(int key) {
        return get(root, key);
    }

    private String get(Node n, int k) {
        if(n == null) {
            return null;
        }
        if(k == n.key) {
            return n.value;
        } else {
            if(k < n.key) {
                return get(n.left, k);
            } else {
                return get(n.right, k);
            }
        }
    }

    //    This snippet puzzles me
    public void put(int key, String value) {
        root = put(root, key, value);
    }

    private Node put(Node n, int k, String v) {
        if(n == null) {
            return new Node(k, v, 1);
        }
        if(n.key == k) {
            n.value = v;
        } else {
            if(k < n.key) {
                n.left = put(n.left, k, v);
            } else {
                n.right = put(n.right, k, v);
            }
        }
        n.N = size(n.left) + size(n.right);
        return n;
    }
    //    snippet ends


    public static void main(String[] args) {
        BST r = new BST();
        r.put(2, "root");
        r.put(1, "left");
        r.put(3, "right");

        System.out.println(r.get(2));
        System.out.println(r.get(1));
        System.out.println(r.get(3));
    }


}

输出:

root
left
right

效果很好:)

但是，当我像这样更改 put 方法时:

    public void put(int key, String value) {
        put(root, key, value);
    }

    private void put(Node n, int k, String v) {
        if(n == null) {
            n = new Node(k, v, 1);
        }
        if(n.key == k) {
            n.value = v;
        } else {
            if(k < n.key) {
                put(n.left, k, v);
            } else {
                put(n.right, k, v);
            }
        }
        n.N = size(n.left) + size(n.right);
    }

我得到了输出

null
null
null

显然，新的 put 方法失败了。但为什么？在我看来，这两种不同的实现并没有太大区别。

Answer 1

当您更改分配时

n.left = put(n.left, k, v);

至

put(n.left, k, v);

(或与 n.right 相同)，并且您在那里还没有节点，您正在为 n 变量分配一个新节点，但您没有更新从父级到子级的链接从递归调用返回时。因此，新节点将保持隔离，因为您要更改上次递归调用中 n 的引用，而不是 n.left(或 right)父级的引用。此外，我猜测当引用 n 的值将在最后一次递归调用结束时被释放时，由于没有其他引用指向新创建的节点，这最终将被垃圾收集器消除。