Рекурсивный механизм для поиска максимальной глубины глубины двоичного дерева очень прост, но как мы можем сделать это эффективно без рекурсии, поскольку у меня есть большое дерево, где я бы предпочел избежать этой рекурсии.
//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.
В этом варианте используются два стека, один для изучения дополнительных узлов (wq), и один из них всегда содержит текущий путь от корня (path). Когда мы видим тот же самый node в верхней части обоих стеков, это означает, что мы изучили все под ним и можем его погладить. Настало время обновить глубину дерева. На случайных или сбалансированных деревьях дополнительное пространство должно быть 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;
}
(Бесстыдный плагин: у меня была идея использовать двойные стеки для нерекурсивных обходов несколько недель назад, проверьте здесь код на С++ http://momchil-velikov.blogspot.com/2013/10/non-recursive-tree-traversal.html не то, что я утверждаю, что я первый придумал это:)
Рекурсивный подход, который вы описали, по существу является DFS над двоичным деревом. Вы можете реализовать это итеративно, если хотите, сохраняя явный стек узлов и отслеживая максимальную глубину.
Надеюсь, это поможет!
Я написал следующую логику, чтобы найти максимальную и минимальную глубину, которая не предполагает рекурсии и без увеличения сложности пространства.
// 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;
}
Если вы можете поддерживать левое и правое значения в каждом node, это можно сделать.
http://leetcode.com/2010/04/maximum-height-of-binary-tree.html.
Возможный дубликат: Неверная репликация глубины двоичного дерева node
Другой способ - использовать Level order traversal, где высота дерева равна количеству уровней дерева. (Его можно использовать только для калибровки минимальной высоты дерева.)
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;
}
Использование массива для хранения слоя узлов, каждый раз, когда вы находите новый слой. глубина плюс одна.
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;
}