java - 使用 Java 和递归进行二叉树的级别顺序遍历

Question

我在使用递归时遇到二叉树的级别顺序遍历问题。我输入以下值: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。

Answer 1

有趣的是，这是一个相当常见的问题(谷歌“递归面包首先遍历”，并且有几个类似答案的 stackoverflow 链接)

迄今为止最好的就在这里

Performing Breadth First Search recursively

我同意最佳答案的作者的观点，将迭代算法(广度优先遍历)转变为递归解决方案确实没有意义。正如前面提到的，将迭代转变为尾递归是很容易的，但是这样做的目的是什么？而且你仍然需要排队。