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

Question

我们有一个由0和1组成的二叉树（不是BST）。我们需要从根目录的路径找到最深的1只由1的

来源：亚马逊简短采访Q

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'，则将左边和右边儿童的最大'深度'加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; 
}