Entre los problemas de recorrido de árbol binario de preorden, inorden y postorder, el recorrido de postorder es el más complicado.
Por ejemplo, para el siguiente árbol, el recorrido de la orden de envío devuelve {4, 6, 5, 2, 3, 1}.
Solución Java 1
La clave para el recorrido iterativo del postorder es la siguiente:
- El orden de «Postorder» es: hijo izquierdo -> hijo derecho -> nodo padre.
- Encuentre la relación entre el nodo visitado anteriormente y el nodo actual
- Usa una pila para rastrear nodos
A medida que bajamos por el árbol hasta la izquierda, verifique el nodo visitado anteriormente. Si el nodo actual es el hijo izquierdo o derecho del nodo anterior, continúe bajando por el árbol y agregue el nodo izquierdo / derecho a la pila cuando corresponda. Cuando no hay hijos para el nodo actual, es decir, el nodo actual es una hoja, sáquelo de la pila. Luego, el nodo anterior pasa a estar debajo del nodo actual para el siguiente bucle. Puede usar un ejemplo para recorrer el código.
//Definition for binary tree public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public ArrayList<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> lst = new ArrayList<Integer>(); if(root == null) return lst; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); TreeNode prev = null; while(!stack.empty()){ TreeNode curr = stack.peek(); // go down the tree. //check if current node is leaf, if so, process it and pop stack, //otherwise, keep going down if(prev == null || prev.left == curr || prev.right == curr){ //prev == null is the situation for the root node if(curr.left != null){ stack.push(curr.left); }else if(curr.right != null){ stack.push(curr.right); }else{ stack.pop(); lst.add(curr.val); } //go up the tree from left node //need to check if there is a right child //if yes, push it to stack //otherwise, process parent and pop stack }else if(curr.left == prev){ if(curr.right != null){ stack.push(curr.right); }else{ stack.pop(); lst.add(curr.val); } //go up the tree from right node //after coming back from right node, process parent node and pop stack. }else if(curr.right == prev){ stack.pop(); lst.add(curr.val); } prev = curr; } return lst; } } |
Solución Java 2 – ¡Simple!
Esta solución es simple, pero tenga en cuenta que la estructura del árbol cambia ya que los niños se establecen en nulo.
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if(root==null) { return res; } Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while(!stack.isEmpty()) { TreeNode temp = stack.peek(); if(temp.left==null && temp.right==null) { TreeNode pop = stack.pop(); res.add(pop.val); } else { if(temp.right!=null) { stack.push(temp.right); temp.right = null; } if(temp.left!=null) { stack.push(temp.left); temp.left = null; } } } return res; } |
