2

在使用递归时，我的二叉树的级别顺序遍历存在问题。我正在输入以下值：50,60,70,30,20,10 这是我正在使用的代码：

    public void levelOrder(Node localRoot){
    if(localRoot != null){
        if(localRoot.leftChild != null && localRoot.rightChild != null){
            System.out.print(localRoot.iData + " ");
            System.out.print(localRoot.leftChild.iData + " ");
            System.out.print(localRoot.rightChild.iData + " ");
            levelOrder(localRoot.leftChild);
            levelOrder(localRoot.rightChild);
        }
        else if(localRoot.rightChild == null && localRoot.leftChild == null){
            ;
        }
        else if(localRoot.rightChild == null){
            System.out.print(localRoot.leftChild.iData + " ");
            //levelOrder(localRoot.leftChild);
        }
        else{
            System.out.print(localRoot.rightChild.iData + " ");
            //levelOrder(localRoot.rightChild);
        }
    }
}

不使用堆栈是否可以递归？因为目前这个功能把我一直带到左边然后它向右走。我可以做些什么不同的事情？

我对这段代码的输出是：50、30、60、20、70，它不打印 10。

4

3 回答 3

1

有趣的是，这是一个相当普遍的问题（谷歌“递归面包第一次遍历”并且有几个链接到类似答案的stackoverflow）

到目前为止最好的在这里

递归执行广度优先搜索

我同意最佳答案的作者，将迭代算法（广度优先遍历）转变为递归解决方案确实没有意义。如前所述，是的，将迭代转换为尾递归很容易，但目的是什么？你仍然需要一个队列。

于 2013-11-14T17:24:17.640 回答
1

公共无效级别（）{

 printLevel(root);

}

public void printLevel(Node current)
{
    if(current != null){
        if(current.leftChild != null && current.rightChild != null){
            System.out.print(current.iData + " ");
            System.out.print(current.leftChild.iData + " ");
            System.out.print(current.rightChild.iData + " ");
            printLevel(current.leftChild);
            printLevel(current.rightChild);
        }
        else if(current.rightChild == null && current.leftChild == null){
        ;
        }
        else if(current.rightChild == null){
            System.out.print(current.leftChild.iData + " ");
            //levelOrder(current.leftChild);
        }
        else{
            System.out.print(current.rightChild.iData + " ");
            //levelOrder(current.rightChild);
        }
    }
}
于 2015-05-09T23:52:01.893 回答
0

您可以使用队列来解决问题：

private Queue<Key> getLevelOrderKeys(Node root){

    if (root == null) {
        return null;
    }

    Queue<Key> keyQueue = new ArrayDeque<Key>(); //return value. Queue with the level order keys
    Queue<Node> nodeQueue = new ArrayDeque<Node>();

    nodeQueue.add(root);

    //while there is at least one discovered node
    while(!nodeQueue.isEmpty()) {

        Node current = nodeQueue.poll();
        keyQueue.add(current.key);

        if (current.left != null){
            nodeQueue.add(current.left);
        }

        if (current.right != null){
            nodeQueue.add(current.right);
        }

    }

    return keyQueue;

}
于 2014-12-30T13:46:54.377 回答