通过二叉搜索树迭代查找所有叶子

Question

我对树很新,我正在尝试创建一种"叶子迭代器".我认为它应该将没有.left和.right值的所有节点放在堆栈上,但我不确定它是怎么做的,甚至是不对的.我已经尝试过搜索它,但是我遇到的每个例子都是从最左边的叶子开始,然后继续p = node.parent,我避免链接到节点的父节点.

我不明白我怎么能重复从根开始并经过葡萄藤而不会一遍又一遍地访问相同的葡萄藤.

编辑

我看到人们建议使用递归方法来解决这个问题,我现在同意了.但是我一直试图找到迭代器级方法来解决这个问题,但是我仍然想知道这是否可能,以及如何做到这一点!

Answer 1

使用递归:

public void visitNode(Node node) {
    if(node.left != null) {
        visitNode(node.left);
    }
    if(node.right != null) {
        visitNode(node.right);
    }
    if(node.left == null && node.right == null) {
        //OMG! leaf!
    }
}

通过提供root:

visitNode(root);

为了将其转换为一个Iterator<Node>你必须将递归转换为循环然后遍历状态.非平凡,但应该给你很多乐趣.