java - 使用深度优先搜索迭代回溯

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;
}

但是，我总是无法将递归算法转换为迭代算法，即使递归只是使用程序堆栈。我稍微研究了一下代码，但似乎迭代算法需要一个将子节点链接到其父节点的映射，以便在找到节点时回溯。

我只是想知道是否有更简单的方法，或者最简单的方法是否真的是使用链接父节点和子节点的 map 以便您可以回溯。

谢谢!

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
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);
}

Note: If you tree has two or more nodes has the same value,you need to change some codes.You can try youself.