二叉树 path() 实现

Question

我正在做一个编程作业，它要求我们编写一个路径（根，值）方法，return是一个指向目标节点（值）的方向枚举（左，右）的链表.我们不允许创建任何新字段来实现这一点，这就是我创建 pathHelper() 方法的原因。我失败的测试之一应该是 return: left, right 作为路径，但它是 returning left, right,左，右。我不确定为什么它会计算两次步数。任何建议，将不胜感激！注意：这是一棵二叉树，不是 BST。我们应该使用详尽的 DFS 方法。

    public static <T> LinkedList<BinaryNode.Direction> path(BinaryNode<T> root, T value) {
        if (root == null) {
            return null;
        } else if (root.payload == value) {
            return new LinkedList<>();
        }
        LinkedList<BinaryNode.Direction> list = new LinkedList<>();
        pathHelper(root, value, list);
        return list;
    }

    public static <T> void pathHelper(BinaryNode<T> root, T value, LinkedList<BinaryNode.Direction> list) {
        if (root.left != null) {
            if (root.payload != value) {
                list.add(BinaryNode.Direction.left);
            }
            pathHelper(root.left, value, list);
        } if (root.right != null) {
            if (root.payload != value) {
                list.add(BinaryNode.Direction.right);
            }
            pathHelper(root.right, value, list);
        }
    }

Answer 1

您的代码中有很多错误，所以我很惊讶所有测试用例都通过了。您似乎在搜索树时而不是在找到值时存储方向。

我怀疑你把问题复杂化了。如果你 return 一个 boolean 从你的辅助函数基于是否找到该项目然后你可以很容易地添加方向时你 return 从递归：

private boolean findPath(BinaryNode<T> node, T value, List<BinaryNode.Direction> directions) {
    if (node == null) {
        return false;
    } else if (node.payload.equals(value)) {
        return true;
    } else if (findPath(node.left, value, directions)) {
        directions.add(0, BinaryNode.Direction.LEFT);
        return true;
    } else if (findPath(node.right, value, directions)) {
        directions.add(0, BinaryNode.Direction.RIGHT);
        return true;
    } else {
        return false;
    }
}

请注意，这会在列表的开头插入方向，以确保其顺序正确。这也允许您检测根具有值的位置，因为它将 return 为真但路径将为空。

二叉树 path() 实现

Binary Tree path() Implementation

java

binary-tree