二叉树中节点到根路径

Question

我试图使用 Leap Of Faith 在二叉树中找到节点到根路径，但我现在卡住了。

它在一些简单的情况下有效，但它 returns 在其他情况下是错误的路径。

例如，对于这棵树：

        1
       / \
      2   3

...并将 3 作为参数传递，它 returns {1, 2} 当需要 {1, 3} 时。

谁能告诉我我的代码有什么问题吗？

public static ArrayList<Integer> nodeToRootPath(Node root, int data) {
    // write your code here
    ArrayList<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    if (root.data == data) {
        res.add(data);
        return res;
    }
    res = nodeToRootPath(root.left, data);
    if (res.size() != 0) {
        res.add(root.data);
        return res;
    }
    else {
        res.clear();
        res = nodeToRootPath(root.right, data);
        res.add(root.data);
        return res;
    }
}

Answer 1

问题是当递归从 right 子树返回时，您的代码不会验证该搜索是否成功。它应该——就像左侧一样——在向它添加任何内容之前检查 res.size() 是否非零。

一些旁注：

当您要在下一行中为 res 分配新值时，无需调用 res.clear()。
遗憾的是，当您最终不在基本情况下时创建一个新列表并忽略创建的新列表，而是使用您从递归调用返回的列表。因此，只有当您知道自己处于基本情况时才创建一个新列表。

这里更正：

public static ArrayList<Integer> nodeToRootPath(Node root, int data) {
    if (root == null) {
        return new ArrayList<>();
    }
    if (root.data == data) {
        return new ArrayList<>(Arrays.asList(data));
    }
    ArrayList<Integer> res = nodeToRootPath(root.left, data);
    if (res.size() == 0) {
        res = nodeToRootPath(root.right, data);
    }
    if (res.size() != 0) {
        res.add(root.data);
    }
    return res;
}

二叉树中节点到根路径

Node to root path in Binary Tree

java

tree