Hay 3 soluciones para resolver este problema.
Solución Java 1: iterativa
La clave para resolver el recorrido en orden del árbol binario incluye lo siguiente:
- El orden de «inorder» es: hijo izquierdo -> padre -> hijo derecho
- Usa una pila para rastrear nodos
public List<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> result = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode p = root; while(p!=null){ stack.push(p); p=p.left; } while(!stack.isEmpty()){ TreeNode t = stack.pop(); result.add(t.val); t = t.right; while(t!=null){ stack.push(t); t = t.left; } } return result; } |
Solución Java 2: recursivo
La solución recursiva es trivial.
public class Solution { List<Integer> result = new ArrayList<Integer>(); public List<Integer> inorderTraversal(TreeNode root) { if(root !=null){ helper(root); } return result; } public void helper(TreeNode p){ if(p.left!=null) helper(p.left); result.add(p.val); if(p.right!=null) helper(p.right); } } |
Solución Java 3: simple
La siguiente solución es simple, pero cambia la estructura del árbol, es decir, elimina los punteros a los elementos secundarios izquierdo y derecho.
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); if(root==null) return result; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while(!stack.isEmpty()){ TreeNode top = stack.peek(); if(top.left!=null){ stack.push(top.left); top.left=null; }else{ result.add(top.val); stack.pop(); if(top.right!=null){ stack.push(top.right); } } } return result; } |
