Dado el siguiente árbol binario perfecto,
1
/
2 3
/ /
4 5 6 7
Después de llamar a su función, el árbol debería verse así:
1 -> NULL
/
2 -> 3 -> NULL
/ /
4->5->6->7 -> NULL
Solución Java 1 – Simple
public void connect(TreeLinkNode root) { if(root==null) return; LinkedList<TreeLinkNode> nodeQueue = new LinkedList<TreeLinkNode>(); LinkedList<Integer> depthQueue = new LinkedList<Integer>(); if(root!=null){ nodeQueue.offer(root); depthQueue.offer(1); } while(!nodeQueue.isEmpty()){ TreeLinkNode topNode = nodeQueue.poll(); int depth = depthQueue.poll(); if(depthQueue.isEmpty()){ topNode.next = null; }else if(depthQueue.peek()>depth){ topNode.next = null; }else{ topNode.next = nodeQueue.peek(); } if(topNode.left!=null){ nodeQueue.offer(topNode.left); depthQueue.offer(depth+1); } if(topNode.right!=null){ nodeQueue.offer(topNode.right); depthQueue.offer(depth+1); } } } |
Solución Java 2
Esta solución es más fácil de entender. Puede utilizar el árbol de ejemplo anterior para recorrer el algoritmo. La idea básica es tener 4 punteros para moverse hacia la derecha en dos niveles (ver comentarios en el código).
public void connect(TreeLinkNode root) { if(root == null) return; TreeLinkNode lastHead = root;//prevous level's head TreeLinkNode lastCurrent = null;//previous level's pointer TreeLinkNode currentHead = null;//currnet level's head TreeLinkNode current = null;//current level's pointer while(lastHead!=null){ lastCurrent = lastHead; while(lastCurrent!=null){ if(currentHead == null){ currentHead = lastCurrent.left; current = lastCurrent.left; }else{ current.next = lastCurrent.left; current = current.next; } if(currentHead != null){ current.next = lastCurrent.right; current = current.next; } lastCurrent = lastCurrent.next; } //update last head lastHead = currentHead; currentHead = null; } } |
