算法：二叉树还原

1. 二叉树的还原简介

二叉树的还原：指的是通过二叉树的遍历序列，还原出对应的二叉树。

从二叉树的遍历过程可以看出，给定一棵非空二叉树，它的前序、中序、后续遍历所得到的遍历序列都是唯一的。那么反过来，如果已知节点的某种遍历序列，能否确定这棵二叉树呢？并且确定的二叉树是否是唯一的呢？

我们先来回顾一下二叉树的前序遍历、中序遍历、后序遍历规则。

非空二叉树的前序遍历规则：
1. 访问根节点。
2. 以前序遍历的方式遍历根节点的左子树。
3. 以前序遍历的方式遍历根节点的右子树。
非空二叉树的中序遍历规则：
1. 以中序遍历的方式遍历根节点的左子树。
2. 访问根节点。
3. 以中序遍历的方式遍历根节点的右子树。
非空二叉树的后序遍历规则：
1. 以后序遍历的方式遍历根节点的左子树。
2. 以后序遍历的方式遍历根节点的右子树。
3. 访问根节点。

先来看二叉树的前序遍历，前序遍历过程中首先访问的是根节点，所以通过前序遍历序列，我们可以确定序列的第 1 个节点肯定是根节点。但是从第 2 个节点开始就不确定它是根节点的左子树还是根节点的右子树了。所以单凭前序遍历序列是无法恢复一棵二叉树的。

再来看二叉树的后序遍历，后序遍历也是只能确定序列的最后一个节点为根节点，而无法确定其他节点在二叉树中的位置。所以单凭后序遍历序列也是无法恢复一棵二叉树的。

最后我们来看二叉树的中序遍历，中序遍历是先遍历根节点的左子树，然后访问根节点，最后遍历根节点的右子树。这样，根节点在中序遍历序列中必然将中序序列分割成前后两个子序列，其中前一个子序列是根节点的左子树的中序遍历序列，后一个子序列是根节点的右子树的中序遍历序列。当然单凭中序遍历序列也是无法恢复一棵二叉树的。

但是如果我们可以将「前序遍历序列」和「中序遍历序列」相结合，那么我们就可以通过上面中序遍历序列中的两个子序列，在前序遍历序列中找到对应的左子序列和右子序列。在前序遍历序列中，左子序列的第 1 个节点是左子树的根节点，右子序列的第 1 个节点是右子树的根节点。这样，就确定了二叉树的 3 个节点。

同时，左子树和右子树的根节点在中序遍历序列中又可以将左子序列和右子序列分别划分成两个子序列。如此递归下去，当确定了前序遍历序列中的所有节点时，我们就得到了一棵二叉树。

还有一个问题，通过前序序列和中序序列还原的二叉树是唯一的吗？

这个唯一性可以利用归纳法加以证明。感兴趣的读者可以试试自己证明或者参考有关资料。

通过上述过程说明：如果已知一棵二叉树的前序序列和中序序列，可以唯一地确定这棵二叉树。

同理，如果已知一棵二叉树的中序序列和后序序列，也可以唯一地确定这棵二叉树。 方法和通过二叉树的前序序列和中序序列构造二叉树类似，唯一不同点在于二叉树的根节点是根据后序遍历序列的最后一个元素确定的。

类似的，已知二叉树的「中序遍历序列」和「层序遍历序列」，也可以唯一地确定一棵二叉树。

需要注意的是：如果已知二叉树的「前序遍历序列」和「后序遍历序列」，是不能唯一地确定一棵二叉树的。 这是因为没有中序遍历序列无法确定左右部分，也就无法进行子序列的分割。

只有二叉树中每个节点度为 2 或者 0 的时候，已知前序遍历序列和后序遍历序列，才能唯一地确定一颗二叉树，如果二叉树中存在度为 1 的节点时是无法唯一地确定一棵二叉树的，这是因为我们无法判断该节点是左子树还是右子树。

2. 从前序和中序遍历序列构造二叉树

描述：已知一棵二叉树的前序遍历序列和中序遍历序列。
要求：构造出该二叉树。
注意：假设树中没有重复的元素。

class TreeNode {  
    int val;  
    TreeNode left;  
    TreeNode right;  
  
    TreeNode(int val) {  
        this.val = val;  
    }  
}  
  
public class Solution {  
    public TreeNode buildTree(int[] preorder, int[] inorder) {  
        if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) {  
            return null;  
        }  
        return createTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);  
    }  
  
    private TreeNode createTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {  
        if (preStart > preEnd || inStart > inEnd) {  
            return null;  
        }  
  
        // 前序遍历的第一个节点是当前子树的根节点  
        TreeNode root = new TreeNode(preorder[preStart]);  
  
        // 在中序遍历中找到根节点的索引  
        int rootIndex = 0;  
        for (int i = inStart; i <= inEnd; i++) {  
            if (inorder[i] == root.val) {  
                rootIndex = i;  
                break;  
            }  
        }  
  
        // 递归构建左子树和右子树  
        root.left = createTree(preorder, preStart + 1, preStart + rootIndex - inStart, inorder, inStart, rootIndex - 1);  
        root.right = createTree(preorder, preStart + rootIndex - inStart + 1, preEnd, inorder, rootIndex + 1, inEnd);  
  
        return root;  
    }  
}

3. 从中序和后序遍历序列构造二叉树

描述：已知一棵二叉树的中序遍历序列和后序遍历序列。
要求：构造出该二叉树。
注意：假设树中没有重复的元素。

class TreeNode {  
    int val;  
    TreeNode left;  
    TreeNode right;  
  
    TreeNode(int val) {  
        this.val = val;  
    }  
}  
  
public class Solution {  
    public TreeNode buildTree(int[] inorder, int[] postorder) {  
        if (inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0) {  
            return null;  
        }  
        return createTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);  
    }  
  
    private TreeNode createTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {  
        if (inStart > inEnd || postStart > postEnd) {  
            return null;  
        }  
  
        // 后序遍历的最后一个节点是当前子树的根节点  
        int rootVal = postorder[postEnd];  
        TreeNode root = new TreeNode(rootVal);  
  
        // 在中序遍历中找到根节点的索引  
        int rootIndex = 0;  
        for (int i = inStart; i <= inEnd; i++) {  
            if (inorder[i] == rootVal) {  
                rootIndex = i;  
                break;  
            }  
        }  
  
        // 递归构建右子树（先构建右子树是因为后序遍历的顺序是左-右-根）  
        root.right = createTree(inorder, rootIndex + 1, inEnd, postorder, postStart + rootIndex - inStart, postEnd - 1);  
        // 递归构建左子树  
        root.left = createTree(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + rootIndex - inStart - 1);  
  
        return root;  
    }  
}

4. 从前序和后序遍历序列构造二叉树

已知二叉树的前序遍历序列和后序遍历序列，是不能唯一地确定一棵二叉树的。 而如果不要求构造的二叉树是唯一的，只要求构造出一棵二叉树，还是可以进行构造的。

描述：已知一棵二叉树的前序遍历序列和后序遍历序列。
要求：重构并返回该二叉树。
注意：假设树中没有重复的元素。如果存在多个答案，则可以返回其中任意一个。

class TreeNode {  
    int val;  
    TreeNode left;  
    TreeNode right;  
  
    TreeNode(int val) {  
        this.val = val;  
    }  
}  
  
public class Solution {  
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {  
        if (preorder == null || postorder == null || preorder.length == 0 || postorder.length == 0) {  
            return null;  
        }  
        return createTree(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);  
    }  
  
    private TreeNode createTree(int[] preorder, int preStart, int preEnd, int[] postorder, int postStart, int postEnd) {  
        if (preStart > preEnd || postStart > postEnd) {  
            return null;  
        }  
  
        // 前序遍历的第一个节点是当前子树的根节点  
        TreeNode root = new TreeNode(preorder[preStart]);  
  
        // 如果只有一个节点，直接返回  
        if (preStart == preEnd) {  
            return root;  
        }  
  
        // 在后序遍历中找到左子树中最后一个节点的索引  
        int leftSubtreeSize = 0;  
        for (int i = postStart; i <= postEnd; i++) {  
            if (postorder[i] == preorder[preStart + 1]) {  
                leftSubtreeSize = i - postStart + 1;  
                break;  
            }  
        }  
  
        // 递归构建左子树和右子树  
        root.left = createTree(preorder, preStart + 1, preStart + leftSubtreeSize, postorder, postStart, postStart + leftSubtreeSize - 1);  
        root.right = createTree(preorder, preStart + leftSubtreeSize + 1, preEnd, postorder, postStart + leftSubtreeSize, postEnd - 1);  
  
        return root;  
    }  
}