根据前序、中序、后序遍历的结果还原二叉树
- 已知二叉树的前序遍历和中序遍历可以得到原二叉树
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public class BuildTree { /** * 根据前序和中序还原原二叉树 */ public static Tree buildTreeThroughPreIn(int[] preorder, int[] inorder) { if (preorder == null || inorder == null) { return null; } return buildTreeThroughPreIn(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); } private static Tree buildTreeThroughPreIn(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) { if (preStart > preEnd || inStart > inEnd) { return null; } Tree root = new Tree(pre[preStart]); for (int i = inStart; i <= inEnd; i++) { if (in[i] == pre[preStart]) { root.left = buildTreeThroughPreIn(pre, preStart + 1, preStart + i - inStart, in, inStart, i - 1); root.right = buildTreeThroughPreIn(pre, preStart + i - inStart + 1, preEnd, in, i + 1, inEnd); break; } } return root; } } |
- 同样已知二叉树的中序遍历和后序遍历可以得到原二叉树
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
public class BuildTree { static int pInorder; static int pPostorder; /** * 根据后序和中序还原原二叉树 */ public static Tree buildTreeThroughInPost(int[] inorder, int[] postorder) { pInorder = inorder.length - 1; pPostorder = postorder.length - 1; return buildTreeThroughInPost(inorder, postorder, null); } private static Tree buildTreeThroughInPost(int[] inorder, int[] postorder, Tree end) { if (pPostorder < 0) { return null; } // 创建根节点 Tree root = new Tree(postorder[pPostorder--]); // if right node exist, create right subtree if (inorder[pInorder] != root.value) { root.right = buildTreeThroughInPost(inorder, postorder, root); } pInorder--; // 左节点存在，创建左子树 if ((end == null) || (inorder[pInorder] != end.value)) { root.left = buildTreeThroughInPost(inorder, postorder, end); } return root; } } |
|
1 2 3 4 5 6 7 8 9 |
public class Tree { public int value; public Tree left; public Tree right; Tree(int value) { this.value = value; } } |
暂无评论