我需要在二叉树中打印一个节点的祖先。例如,节点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
列表将被反转。