El recorrido de árbol binario por adelantado es un problema clásico de entrevista. La clave para resolver este problema es usar una pila para almacenar los niños izquierdo y derecho, y empujar al niño derecho primero para que se procese después del niño izquierdo.
Solución Java
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> returnList = new ArrayList<Integer>(); if(root == null) return returnList; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while(!stack.empty()){ TreeNode n = stack.pop(); returnList.add(n.val); if(n.right != null){ stack.push(n.right); } if(n.left != null){ stack.push(n.left); } } return returnList; } } |
