Итеративное решение для поиска, если дерево сбалансировано

Question

Итак, кто-то опубликовал их решение, но я обнаружил, что он не работает, я разместил его там, но я хотел сделать его более доступным для других.

Вопрос заключается в «Крекинг интервью код», и это первый вопрос, дерево, не стесняйтесь, чтобы сделать другие предложения (или доказать, что я не прав!)

Answer 1

Ключевым моментом здесь является то, что трудно следить возможных путей и их высоты с одним стеком.

То, что я закончил, это толкать как левую, так и правую дочернюю высоту в стек, проверяя, находятся ли они друг в друге, добавив один к максимуму, а затем нажав на него в стек после того, как он выскочил влево и вправо выкл.

я прокомментировал, так что я надеюсь, что это достаточно

/* Returns true if binary tree with root as root is height-balanced */ 
     boolean isBalanced(Node root) { 
      if(root == null) return false; 

      Deque<Integer> heights = new LinkedList<>(); 
      Deque<Node> trail = new LinkedList<>(); 
      trail.push(root); 

      Node prev = root; //set to root not null to not confuse when root is misisng children 

      while(!trail.isEmpty()) { 
       Node curr = trail.peek(); //get the next node to process, peek because we need to maintain trail until we return 

       //if we just returned from left child 
       if (curr.left == prev) { 
        if(curr.right != null) trail.push(curr.right); //if we can go right go 
        else { 
         heights.push(-1); //otherwise right height is -1 does not exist and combine heights 
         if(!combineHeights(heights)) return false; 
         trail.pop(); //back to parent 
        } 
       } 
       //if we just returned from right child 
       else if (curr.right == prev) { 
        if(!combineHeights(heights)) return false; 
        trail.pop(); //up to parent 
       } 
       //this came from a parent, first thing is to visit the left child, or right if no left 
       else { 
        if(curr.left != null) trail.push(curr.left); 
        else { 
         if (curr.right != null) { 
          heights.push(-1); //no left so when we combine this node left is 0 
          trail.push(curr.right); //since we never go left above logic does not go right, so we must here 
         } 
         else { //no children set height to 1 
          heights.push(0); 
          trail.pop(); //back to parent 
         } 
        } 
       } 

       prev = curr; 
      } 

      return true; 
     } 

     //pop both previous heights and make sure they are balanced, if not return false, if so return true and push the greater plus 1 
     private boolean combineHeights(Deque<Integer> heights) { 
      int rightHeight = heights.pop(); 
      int leftHeight = heights.pop(); 

      if(Math.abs(leftHeight - rightHeight) > 1) return false; 
      else heights.push(Math.max(leftHeight, rightHeight) + 1); 
      return true; 
     } 

Answer 2

оригинальный вопрос в книге ясно, не говоря уже о дереве будучи двоичную. Я, случается, решаю тот же вопрос, но закодирован в Python. Итак, вот мое итерационное решение проблемы, для общих деревьев (где дочерние узлы хранятся в списке), в python.

def is_balanced_nonrecursive(self): 
    stack = [self.root] 
    levels = [0] 
    current_min = sys.maxint 
    current_max = 0 
    current_level = 0 
    while len(stack) > 0: 
     n = stack.pop() 
     current_level = levels.pop() 
     for c in n.children: 
      stack.append(c) 
      levels.append(current_level + 1) 
     if len(n.children) == 0: 
      if current_level < current_min: 
       current_min = current_level 
      if current_level > current_max: 
       current_max = current_level 
    return current_max - current_min < 2 

Это, в основном, первый проход по дереву. Мы сохраняем отдельный стек для уровней (список levels). Если мы увидим какой-либо листовой узел, мы соответственно обновим текущие минимальные и максимальные уровни. Алгоритм пересекает все дерево и в конце, если уровни max и min отличаются более чем одним, тогда дерево не сбалансировано.

Существует множество оптимизаций, например, проверка того, является ли разность min и max более чем одной внутри цикла, и если это так, то немедленно возвратите False.