如何在二叉树中找到从只包含1的根开始的最深路径？

Question

我们有一个只由0和1组成的二叉树(不是BST)。我们需要找到最深的1，其中从root开始的路径仅由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’深度上加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;
}