Dado un árbol binario completo, cuente el número de nodos.
La solución a este problema puede ser tan simple como la siguiente:
public int countNodes(TreeNode root) { if(root == null){ return 0; } return 1 + countNodes(root.left) + countNodes(root.right); } |
Las siguientes dos soluciones son mejoras de esta solución. La idea es que podamos saltarnos algunos elementos para reducir el tiempo en el caso medio.
Solución Java 1
Pasos para solucionar este problema:
1) obtenga la altura de la parte más a la izquierda
2) obtenga la altura de la parte más a la derecha
3) cuando son iguales, el # de nodos = 2 ^ h -1
4) cuando no son iguales, obtenga de forma recursiva # de nodos de los subárboles izquierdo y derecho
public int countNodes(TreeNode root) { if(root==null) return 0; int left = getLeftHeight(root)+1; int right = getRightHeight(root)+1; if(left==right){ return (2<<(left-1))-1; }else{ return countNodes(root.left)+countNodes(root.right)+1; } } public int getLeftHeight(TreeNode n){ if(n==null) return 0; int height=0; while(n.left!=null){ height++; n = n.left; } return height; } public int getRightHeight(TreeNode n){ if(n==null) return 0; int height=0; while(n.right!=null){ height++; n = n.right; } return height; } |
Cada vez, tendrá que hacer recorridos a lo largo de los bordes izquierdo y derecho. En el nivel h, iteras cero veces (sin hijo). En el nivel h – 1, itera una vez (un hijo). Etcétera. Entonces eso es 0 + 1 + 2 + … + h pasos solo para calcular los bordes izquierdos, que es h (1 + h) / 2 = O (h ^ 2).
La parte countNodes tiene f (n) = 2 * 2 … * 2 = 2 ^ h, que es el número de nodos. Por lo tanto, la complejidad del tiempo está limitada por O (n) donde n es el número de nodos en el árbol.
Solución Java 2
public int countNodes(TreeNode root) { int h = getHeight(root); int total = (int)Math.pow(2, h)-1; //get num missed int[] miss = new int[1]; helper(root, 0, h, miss); return total - miss[0]; } //true continue, false stop private boolean helper(TreeNode t, int level, int height, int[] miss){ if(t!=null){ level++; }else{ return true; } if(level >=height){ return false; } if(level == height-1){ if(t.right == null){ miss[0]++; } if(t.left == null){ miss[0]++; } if(t.left!=null){ return false; } } boolean r = helper(t.right, level, height, miss); if(r){ boolean l = helper(t.left, level, height, miss); return l; } return true; } private int getHeight(TreeNode root){ TreeNode p = root; int h = 0; while(p!=null){ h++; p = p.left; } return h; } |
La suma del nodo total también se puede escribir como:
int total = (2 << (h-1)) - 1; |
La complejidad de tiempo promedio es O (n / 2), que es la mitad del número de nodos en el árbol.
