Как найти самый глубокий путь от корня, состоящего только из 1, в бинарном дереве поиска? - PullRequest
Новая
       3

Как найти самый глубокий путь от корня, состоящего только из 1, в бинарном дереве поиска?

5 голосов
/ 24 мая 2011

У нас есть двоичное дерево (не BST), состоящее только из 0 и 1. нам нужно найти самую глубокую 1 с путем от корня, состоящим только из 1

Источник: интервью Амазонки Q

1 Ответ

9 голосов
/ 24 мая 2011 
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;
}
...