0

二分木でノードの祖先を出力する必要があります。たとえば、ノード 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 "";  
}
4

3 に答える 3

3 
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リストが逆になることに注意してください。

于 2012-08-21T10:04:43.757 に答える
0

ここにJavaの実装があります

public static List<Integer> ancestors(BinaryTreeNode<Integer> root, Integer target) {
    List<Integer> result = new ArrayList<Integer>();
    findAncestors(root, target, result);
    return result;
}

private static boolean findAncestors(BinaryTreeNode<Integer> node, Integer target, List<Integer> result) {
    if (node == null) {
        return false;
    }
    if (node.getData() == target) {
        return true;
    }
    if (findAncestors(node.getLeft(), target, result) || findAncestors(node.getRight(), target, result)) {
        result.add(node.getData());
        return true;
    }

    return false;
}

単体テストケースはこちら

@Test
public void allAncestors() {
    BinaryTreeNode<Integer> root = buildTree();
    List<Integer> ancestors = BinaryTreeUtil.ancestors(root, 6);
    assertThat(ancestors.toArray(new Integer[0]), equalTo(new Integer[]{5,2,1}));
}
于 2016-04-10T09:37:22.373 に答える