我需要在二叉树中打印一个节点的祖先。例如,节点7的祖先是1,3我已经写了下面的代码,但输出是7。你能提出这段代码中的问题吗?

    1
   / \
  2   3
 / \ / \
4  5 6  7

 public static String findAncestor(BinaryTreeNode root , int number,  boolean matched) {

    if (root != null) {

        int rootData = root.getData();

        BinaryTreeNode left = root.getLeft();
        BinaryTreeNode right = root.getRight();

        if (left != null && right != null) {
            return findAncestor (root.getLeft(), number, matched ) + findAncestor (root.getRight(), number, matched);
        }

        if (left != null) {
            return findAncestor (root.getLeft(), number, matched ) ;
        }

        if (right != null) {
            return findAncestor (root.getRight(), number, matched ) ;
        }

        if (rootData == number) {
            matched = true;
            return String.valueOf(rootData);
        }
        if (matched) {
            return String.valueOf(rootData);
        }
    }
    return "";
}

最佳答案

public boolean findAncestorPath(List<Integer> ancestors, BinaryTreeNode node, int number) {
    if (node == null)
        return false;

    int data = node.getData();
    if (data == number)
        return true;

    if (findAncestorPath(ancestors, node.getLeft(), number)) {
        ancestors.add(data);
        return true;
    }

    if (findAncestorPath(ancestors, node.getRight(), number)) {
        ancestors.add(data);
        return true;
    }

    return false;
}

然后将其称为(您可能还应该将其包装在函数中):
List<Integer>() ancestors = new ArrayList<Integer>();
boolean found = findAncestorPath(ancestors, root, number);

请注意,ancestor列表将被反转。

09-10 08:39
查看更多