java - 递归填充溢出

Question

在看一个 SO 问题时，我建议递归地填充节点网格，我想我应该自己尝试代码，以下内容不断溢出

public class Node {

private Node left;
private Node right;
private Node up;
private Node down;
private int x;
private int y;

public Node(int x, int y) {
    this.x = x;
    this.y = y;
}

public static void buildGrid(Node node) {
    fill(node);
}

private static void fill(Node node) {
    fillLeft(node);
    fillRight(node);
}

private static void fillRight(Node node) {
    if (node.right != null || node.x > 10)
        return;

    node.right = new Node(node.x + 1, node.y);
    fill(node.right);
}

private static void fillLeft(Node node) {
    if (node.left != null || node.x <= 0)
        return;

    node.left = new Node(node.x - 1, node.y);
    fill(node.left);
}

public static void main(String[] args) {
    Node node = new Node(5, 5);
    buildGrid(node);
}

太晚了，我可能错过了非常明显的东西，但为什么会溢出呢？第一次 fillLeft 返回 fill(node.left) 第二次调用 fillLeft(node.left) 应该立即返回，因为 node.left.right != null. fillRight 也一样，不知道哪里出了问题。

堆栈跟踪

Exception in thread "main" java.lang.StackOverflowError
at Node.<init>(Node.java:16)
at Node.fillLeft(Node.java:42)
at Node.fill(Node.java:26)
at Node.fillRight(Node.java:35)
at Node.fill(Node.java:27)
at Node.fillLeft(Node.java:43)
at Node.fill(Node.java:26)
at Node.fillRight(Node.java:35)
at Node.fill(Node.java:27)
at Node.fillLeft(Node.java:43)
at Node.fill(Node.java:26)
at Node.fillRight(Node.java:35)
at Node.fill(Node.java:27)
at Node.fillLeft(Node.java:43)
at Node.fill(Node.java:26)
at Node.fillRight(Node.java:35)
at Node.fill(Node.java:27)
at Node.fillLeft(Node.java:43)
at Node.fill(Node.java:26)
at Node.fillRight(Node.java:35)
at Node.fill(Node.java:27)
at Node.fillLeft(Node.java:43)
at Node.fill(Node.java:26)
at Node.fillRight(Node.java:35)
at Node.fill(Node.java:27)
at Node.fillLeft(Node.java:43)

Answer 1

您的问题是您没有正确地在新节点之间创建链接。你想要:

private static void fillRight(Node node) {
    if (node.right != null || node.x > 10)
        return;

    node.right = new Node(node.x + 1, node.y);
    node.right.left = node; // CURRENT NODE IS LEFT OF NEW NODE!
    fill(node.right);
}

private static void fillLeft(Node node) {
    if (node.left != null || node.x <= 0)
        return;

    node.left = new Node(node.x - 1, node.y);
    node.left.right = node; // CURRENT NODE IS RIGHT OF NEW NODE!
    fill(node.left);
}

如果打印出正在填充的当前节点的坐标，您可以看到它向左移动并振荡，因为“后退”链接始终为 null。将此添加到 fill() 的开头以查看发生了什么:

private static void fill(Node node) {
    System.out.println("filling node " + node.x + " " + node.y + 
                       " " + node.left + " " + node.right); 
    ...

其次:递归网格填充很快变得困惑，很容易导致高递归深度和快速溢出。对于这些类型的事情，您最好使用队列而不是递归地进行。