一、已知前序遍历和中序遍历
假设我们用2个数组preorder和inorder来表示前序和中序遍历的结果。
要生成的二叉树的任意子树都对应于preorder和inorder的某个子数组。该子树的根节点对应于preorder子数组的第一个元素，然后在inorder中查找该该元素。对于inorder中的的子数组，根节点元素左侧的子数组对应左子树，右侧的子数组对应右子树。之后使用递归重复该过程。
下面给出一段Java示例代码：
|
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 |
public class Solution { private int[] preorder; private int[] inorder; public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; this.inorder = inorder; return build(0, 0, preorder.length); } private TreeNode build(int pl, int il, int size){ if(size <= 0) return null; TreeNode root = new TreeNode(preorder[pl]); int m = 0; // m is the size of left sub-tree for(; m < size; m++){ if(inorder[il + m] == root.val) break; } TreeNode left = build(pl + 1, il, m); TreeNode right = build(pl + m + 1, il + m + 1 ,size - m - 1); root.left = left; root.right = right; return root; } } |
二、已知中序遍历和后序遍历
假设我们用2个数组inorder和postorder来表示中序和后序遍历的结果。
与已知前序和中序的情况类似，要生成的二叉树的任意子树都对应于inorder和postorder的某个子数组。该子树的根节点对应于postorder子数组的最后一个元素，然后在inorder中查找该该元素。对于inorder中的的子数组，根节点元素左侧的子数组对应左子树，右侧的子数组对应右子树。之后使用递归重复该过程。
下面给出一段Java示例代码：
|
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 |
public class Solution { private int[] postorder; private int[] inorder; public TreeNode buildTree(int[] inorder, int[] postorder) { this.postorder = postorder; this.inorder = inorder; return build(0, 0, postorder.length); } private TreeNode build(int pl, int il, int size){ if(size <= 0) return null; TreeNode root = new TreeNode(postorder[pl + size - 1]); int m = 0; // m is the size of left sub-tree for(; m < size; m++){ if(inorder[il + m] == root.val) break; } TreeNode left = build(pl, il, m); TreeNode right = build(pl + m, il + m + 1 ,size - m - 1); root.left = left; root.right = right; return root; } } |
三、已知前序遍历和后序遍历
这种情况无法唯一确定一棵二叉树。
一个最简单的例子就是：
前序遍历[1,2]，后序遍历[2,1]。
显然根节点是1，但是节点2既可以是左子节点，也可以使右子节点。无法唯一确定。