用深度优先搜索迭代实现回溯

Question

我正在处理一个编码问题，需要找到节点的路径。使用递归和深度优先搜索（DFS），这非常容易实现。

public ArrayList<Integer> ancestorsList = new ArrayList<Integer>();
public boolean printAncestors(TreeNode root, int nodeData) {

    if (root == null) return false;
    if (root.data == nodeData) return true;

    boolean found = printAncestors(root.left, nodeData) || printAncestors(root.right, nodeData);
    if (found) ancestorsList.add(root.data);

    return found;
}

然而，我总是有问题将递归算法转换为迭代算法，尽管递归只是使用程序堆栈。我对代码进行了一些试验，但似乎迭代算法需要一个将子节点连接到其父节点的映射，以便在找到节点时可以回溯。

我只是想知道是否有更简单的方式，或者最简单的方法是否真的是使用一个将父节点和子节点链接起来的映射，以便您能够回溯。

谢谢！

- Kevin

---

你使用什么数据结构？你能修改你的数据结构吗？如果可以，你可以将父节点添加到TreeNode中或者添加一个标志来标记当前节点是否被访问过。 - TongChen

这将是一个典型的面试类型问题，因此我不能修改数据结构。我可以将节点标记为已访问，但它会告诉我它来自哪个父节点吗？最终所有节点都将被标记为已访问，对吧？ - Kevin

Answer 1

最初的回答：

为了简化代码，我假设节点按值彼此不同。

基本数据结构：

@Getter
@Setter
@AllArgsConstructor
@NoArgsConstructor
@ToString
public class TreeNode implements Comparator<TreeNode> {
    private int value;
    private TreeNode left;
    private TreeNode right;

    @Override
    public int compare(TreeNode o1, TreeNode o2) {
        return o1.getValue() - o2.getValue();
    }
}

查找路径的代码：

private static List<TreeNode> findPath(TreeNode root, int val) {
        if (null == root) {
            return Collections.emptyList();
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        List<TreeNode> path = new ArrayList<>();

        while (!stack.isEmpty()) {
            TreeNode top = stack.pop();
            path.add(top);
            // check the value
            if (top.getValue() == val) {
                break;
            }

            if (top.getRight() != null) {
                stack.push(top.getRight());
            }
            if (top.getLeft() != null) {
                stack.push(top.getLeft());
            }

            // if the node is leaf,we need rollback the path
            if (null == top.getLeft() && null == top.getRight()) {
                if (stack.isEmpty()) {
                  path.clear();
                  break;
                }
                TreeNode nextTop = stack.peek();
                for (int i = path.size() - 1; i >= 0; i--) {
                    if (path.get(i).getRight() == nextTop || path.get(i).getLeft() == nextTop) {
                        path = path.subList(0, i + 1);
                        break;
                    }
                }
            }
        }

        return path;
    }

Test Case:

@Test
public void test_findPath() {
    TreeNode treeNode8 = new TreeNode(8, null, null);
    TreeNode treeNode9 = new TreeNode(9, null, null);
    TreeNode treeNode10 = new TreeNode(10, null, null);
    TreeNode treeNode4 = new TreeNode(4, treeNode8, null);
    TreeNode treeNode5 = new TreeNode(5, treeNode9, treeNode10);
    TreeNode treeNode2 = new TreeNode(2, treeNode4, treeNode5);
    TreeNode treeNode1 = new TreeNode(1, treeNode2, null);
    List<TreeNode> path = TreeNodeService.findPath(treeNode1, 10);
    Assert.assertEquals(path.size(),4);
    Assert.assertEquals(path.get(0).getValue(),1);
    Assert.assertEquals(path.get(1).getValue(),2);
    Assert.assertEquals(path.get(2).getValue(),5);
    Assert.assertEquals(path.get(3).getValue(),10);
}

注意：如果您的树有两个或更多节点具有相同的值，则需要更改一些代码。您可以尝试自己。最初的回答。

- TongChen