2

正在查看一个 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)should 立即返回 since 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)
4

3 回答 3

3

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

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); 
    ...

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

于 2013-11-07T05:13:21.700 回答
1

呼叫fillRight()从 fillRight()和同样为左。

目前它正在创建一个新节点，然后调用fill()这个具有空左/右指针的节点......

于 2013-11-07T05:15:46.000 回答
1

您的 fillLeft 和 fillRight 将永远不会达到条件 node.left != null 和 node.right != null 这将停止递归。

看起来 x 和 y 是您的键，您必须根据 x 和 y 将它们存储在某处，如果它们已经创建而不是始终调用新节点，则将它们取回。

于 2013-11-07T05:29:10.737 回答