Dado un árbol binario, aplánelo a una lista vinculada en el lugar.
Por ejemplo,
Dado
1
/
2 5
/
3 4 6
El árbol aplanado debería verse así:
1
2
3
4
5
6
Solución Java
Baje por el árbol de la izquierda, cuando el niño derecho no sea nulo, empuje al niño derecho a la pila.
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public void flatten(TreeNode root) { Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode p = root; while(p != null || !stack.empty()){ if(p.right != null){ stack.push(p.right); } if(p.left != null){ p.right = p.left; p.left = null; }else if(!stack.empty()){ TreeNode temp = stack.pop(); p.right=temp; } p = p.right; } } } |
