Поиск максимальной глубины двоичного дерева без рекурсии

Question

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

//Recursive mechanism which I want to replace with non-recursive 
private static int maxDepth(Node node) { 
if (node == null) return 0; 
    return 1 + Math.max(maxDepth(node.left), maxDepth(node.right)); 
} 

PS: Я ищу ответы на Java.

Answer 1

Этот вариант использует два стека, один для дополнительных узлов, чтобы исследовать (wq) и один всегда содержащих текущий путь от корня (path). Когда мы видим один и тот же узел в верхней части обоих стеков, это означает, что мы изучили все под ним и можем его всплыть. Настало время обновить глубину дерева. На случайных или сбалансированных деревьях дополнительное пространство должно быть O (log n), в худшем случае O (n), конечно.

static int maxDepth (Node r) { 
    int depth = 0; 
    Stack<Node> wq = new Stack<>(); 
    Stack<Node> path = new Stack<>(); 

    wq.push (r); 
    while (!wq.empty()) { 
     r = wq.peek(); 
     if (!path.empty() && r == path.peek()) { 
      if (path.size() > depth) 
       depth = path.size(); 
      path.pop(); 
      wq.pop(); 
     } else { 
      path.push(r); 
      if (r.right != null) 
       wq.push(r.right); 
      if (r.left != null) 
       wq.push(r.left); 
     } 
    } 

    return depth; 
} 

(Shameless вилка: У меня была эта идея для использования двойных стеков для не рекурсивных обходов несколько недель назад, проверить на C++ код здесь http://momchil-velikov.blogspot.com/2013/10/non-recursive-tree-traversal.html не то, что я утверждаю, что я был первым, кто выдумал :)

Answer 2

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

http://leetcode.com/2010/04/maximum-height-of-binary-tree.html.

Возможный дубликат: Retrieving a Binary-Tree node's depth non-recursively

Answer 3

Рекурсивный подход вы описали, по существу, ДФС над бинарным деревом. Вы можете реализовать это итеративно, если хотите, сохраняя явный стек узлов и отслеживая максимальную глубину.

Надеюсь, это поможет!

Answer 4

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

// Find the maximum depth in the tree without using recursion 
private static int maxDepthNoRecursion(TreeNode root) { 
    return Math.max(maxDepthNoRecursion(root, true), maxDepthNoRecursion(root, false)); 
} 

// Find the minimum depth in the tree without using recursion 
private static int minDepthNoRecursion(TreeNode root) { 
    return Math.min(maxDepthNoRecursion(root, true), maxDepthNoRecursion(root, false)); 
} 

private static int maxDepthNoRecursion(TreeNode root, boolean left) { 
    Stack<TreeNode> stack = new Stack<>(); 
    stack.add(root); 
    int depth = 0; 
    while (!stack.isEmpty()) { 
     TreeNode node = stack.pop(); 
     if (left && node.left != null) stack.add(node.left); 
     // Add the right node only if the left node is empty to find max depth 
     if (left && node.left == null && node.right != null) stack.add(node.right); 
     if (!left && node.right != null) stack.add(node.right); 
     // Add the left node only if the right node is empty to find max depth 
     if (!left && node.right == null && node.left != null) stack.add(node.left); 
     depth++; 
    } 
    return depth; 
} 

Answer 5

Другой способ - использовать Level order traversal, где высота дерева равна количеству уровней дерева. (Это может быть использовать только calulate минимальной высоту дерева.)

public int maxDepth(TreeNode root) { 
    if (root == null) return 0; 
    LinkedList<TreeNode> arr = new LinkedList<TreeNode>(); // queue for current level 
    LinkedList<TreeNode> tmp = new LinkedList<TreeNode>(); // queue for next level 
    arr.add(root); 
    int res = 0; // result 
    TreeNode node; // tmp node 
    while (true) { 
     while (!arr.isEmpty()) { 
      node = arr.poll(); 
      if (node.left != null) tmp.add(node.left); 
      if (node.right != null) tmp.add(node.right); 
     } 
     res++; 
     if (tmp.isEmpty()) break; 
     arr = tmp; 
     tmp = new LinkedList<TreeNode>(); 
    } 
    return res; 
} 

Answer 6

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

public int maxDepth2(TreeNode root){ 
     if(root == null){ 
      return 0; 
     } 

     int depth = 0; 

     ArrayList<TreeNode> oneLayer = new ArrayList<TreeNode>(); 
     oneLayer.add(root); 

     while(!oneLayer.isEmpty()){ 
      ArrayList<TreeNode> newLayer = new ArrayList<TreeNode>(); 
      for(TreeNode node:oneLayer){ 
       if(node.right!=null){ 
        newLayer.add(node.right); 
       } 
       if(node.left!=null){ 
        newLayer.add(node.left); 
       } 
      } 
      oneLayer = newLayer; 
      depth++; 
     } 

     return depth; 
    }