java - 在不使用 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) 添加到“祖先”映射。这张 map 可以让你找到被访问过的任何节点的祖先。
• • 如果 N.right 不为空，则将 (N.right, N) 添加到“祖先”映射中
• • 如果N.left不为空，将其添加到待办事项列表
• • 如果N.right不为空，将其添加到待办事项列表中

在这一点上，目标的 parent 、祖 parent 等，一直向上，将在“祖先” map 中，因此打印所有祖先应该很容易。

如果你为待办事项列表使用堆栈，你应该在 N.left 之前将 N.right 压入堆栈。然后您将按预定顺序遍历树。

如果你对to-do list使用一个队列，让你在末尾添加元素并从头开始检索，那么我认为遍历顺序将是广度优先搜索，其中我们遍历根，然后是下一层的所有节点，然后是下一层的所有节点，等等。

这是我能想到的最简单的答案，它可以为如何不用递归解决其他树遍历问题提供一个模板。 (此外，它还适用于其他类型的图，如果您添加逻辑以确保您不会两次访问一个节点。)就空间效率而言，这不是最佳答案。通过一些思考，您可以想出一种不使用 Map 的算法，并且不会将节点的两个子节点都压入堆栈或队列(因此​​最大堆栈大小将变小)。