如何在二叉搜索树中找到仅由1组成的根最深的路径？

Question

我们有一个仅由0和1组成的二叉树(不是BST).我们需要找到最深的1,其中一条路径只由1组成

资料来源:亚马逊采访问:

Answer 1

public static int findMaxOnesDepth(Node root){

        if(root != null && root.getValue() == 1){
                 return Math.max(1 + findMaxOnesDepth(root.getLeft()), 
                          1 + findMaxOnesDepth(root.getRight());
        }
        else {
            return 0;
        }
}

如果您所在的节点为'0',那么'1'的深度为0.否则,如果您所在的节点为'1',则将左侧和右侧的最大"深度"加1合适的孩子 - 并返回最大的孩子.

上面的代码找到了长度,为了找到路径上的实际节点,你可以使用一个列表来跟踪它

public static ArrayList<Node> findLongestOnesPath(Node root){

       ArrayList<Node> currStack = new ArrayList<Node>();

      if( root != null && root.getValue() == 1){

          currStack.add(root);

          ArrayList<Node> leftStack = findLongestOnesPath(root.getLeft());
          ArrayList<Node> rightStack = findLongestOnesPath(root.getRight());

          if(leftStack.size() > rightStack.size()){
                currStack.addAll(leftStack);
          }
          else{
              currStack.addAll(rightStack);
          }

      }

      return currStack;
}