0

I need to print the ancestors of a node in binary tree. e.g Node 7 has ancestors as 1,3 . I have written the below code but output is coming as 7. Can you suggest the issues in this code?

    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 回答
-1

这段代码可以很好地给所有祖先一个特定的 node ， node 是根节点， value 是我们必须找到所有祖先的节点的值。

static boolean flag=false;
  static void AnchersterOf(AnchesterNode node,int value) {
        // TODO Auto-generated method stub
      if(node==null)
          return ;

      if(node.value==value){

          flag=true;
          return;
      }

     if(flag==false){
      AnchersterOf(node.left,value);
      if(flag==true){
            AnchersterOf(node,value);

      } if(flag==true)
      System.out.println(node.value);
    AnchersterOf(node.right,value);
    if(flag==true)
          System.out.println(node.value);
     }





    }
于 2017-06-03T16:27:56.127 回答