Dado el recorrido en orden y posorden de un árbol, construya el árbol binario.
Análisis
Este problema se puede ilustrar con un ejemplo sencillo.
in-order: 4 2 5 (1) 6 7 3 8 post-order: 4 5 2 6 7 8 3 (1)
A partir de la matriz posterior al pedido, sabemos que el último elemento es la raíz. Podemos encontrar la raíz en una matriz ordenada. Luego, podemos identificar los subárboles izquierdo y derecho de la raíz a partir de la matriz en orden.
Usando la longitud del subárbol izquierdo, podemos identificar los subárboles izquierdo y derecho en una matriz posterior al pedido. Recursivamente, podemos construir el árbol.
Para este ejemplo, el árbol construido es:
Solución Java
public TreeNode buildTree(int[] inorder, int[] postorder) { int inStart = 0; int inEnd = inorder.length - 1; int postStart = 0; int postEnd = postorder.length - 1; return buildTree(inorder, inStart, inEnd, postorder, postStart, postEnd); } public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) { if (inStart > inEnd || postStart > postEnd) return null; int rootValue = postorder[postEnd]; TreeNode root = new TreeNode(rootValue); int k = 0; for (int i = 0; i < inorder.length; i++) { if (inorder[i] == rootValue) { k = i; break; } } root.left = buildTree(inorder, inStart, k - 1, postorder, postStart, postStart + k - (inStart + 1)); // Becuase k is not the length, it it need to -(inStart+1) to get the length root.right = buildTree(inorder, k + 1, inEnd, postorder, postStart + k- inStart, postEnd - 1); // postStart+k-inStart = postStart+k-(inStart+1) +1 return root; } |
