在二叉树中打印给定输入节点的祖先节点，而无需在 Java 中使用递归

Question

如何在没有递归的情况下获取二叉树的祖先节点。我有以下使用递归的代码，但无法弄清楚如何在不使用递归的情况下获取。

boolean printAncestors(Node node, int target) {        
    /* base cases */
    if (node == null) {
        return false;
    }
    if (node.data == target) {
        return true;
    }
    /* If target is present in either left or right subtree of this node then print this node */
    if (printAncestors(node.left, target) || printAncestors(node.right, target)) {
        System.out.print(node.data + " ");
        return true;
    }
    /* Else return false */
    return false;
}

Answer 1

一种简单的方法涉及某种"待办事项列表"，以及跟踪祖先Map。 待办事项列表可以是队列或堆栈。 基本计划是这样的：

• 初始化待办事项列表以仅包含根目录
• 虽然待办事项列表不为空：
• • 从待办事项列表中获取下一个节点 N
• • 如果 N 是您的目标，请停止
• • 如果 N.left 不为空，请将 （N.left， N） 添加到"祖先"映射中。 此地图将允许您找到访问的任何节点的祖先。
• • 如果 N.right 不为空，则将 （N.right， N） 添加到"祖先"映射
• • 如果 N.left 不为空，请将其添加到待办事项列表中
• • 如果 N.right 不为 null，请将其添加到待办事项列表中

到那时，目标的父代、祖父母等，一直到链条上，都会在"祖先"地图中，所以应该很容易打印出所有的祖先。

如果将堆栈用于待办事项列表，则应在N.left之前将N.right推送到堆栈上。 然后，您将按预顺序遍历树。

如果您为待办事项列表使用队列，以便将元素添加到末尾并从头开始检索它们，那么我认为遍历顺序将是广度优先搜索，其中我们遍历根，然后是下一级的所有节点，然后是该级别上的所有节点，依此类推。

这是我能想到的最简单的答案，它可以提供一个模板，说明如何在没有递归的情况下解决其他树遍历问题。 （此外，它适用于其他类型的图形，如果您添加逻辑以确保您不会两次访问节点。 就空间效率而言，这不是最佳答案。 经过一些思考，您可以想出一种不使用Map的算法，并且不会将节点的两个子节点都推送到堆栈或队列上（因此最大堆栈大小会更小）。