二叉树的还原恢复_二叉树有重复节点怎么还原

二叉树的三种遍历常用于恢复：先序，中序，后序。

1.对于先+中，后+中这两种组合，对任意二叉树的恢复都有唯一解，

2.但对先+后的情况则不是，这种情况下要满足要求：对所有非叶节点，其两个子节点都存在，也即，一个节点要么是叶节点，要么有两个节点。

典型的恢复方法是递归建构节点的左，右子树。

一个一个看：

假设二叉树原型如下，为了方便，节点的值刚好等于层次遍历索引

先序：1,2,4,5,10,11,3,6,7,

中序：4,2,10,5,11,1,6,3,7,

后序：4,10,11,5,2,6,7,3,1,

先+中恢复：

对先序，注意第一个节点是根节点，其遍历顺序是中左右，因此，若把第一个节点作为基准，则其左右子树连续存储在该节点之后，不过，目前我们还不知道到底左右子树的分界点在哪，因此需要结合中序来确定其分界点。先序的第一个节点在中序的第5个位置（从0开始算），而我们知道中序的存储顺序是：先中后，因此，对中序列，该节点的左边是其左子树，右边是右子树。因此，根据节点在中序中的位置可以确定其左子树的元素个数，对应到先序即可得到该节点的左，右子树分别在先，中序的位置。根据上述信息就可递归的恢复根节点的左，右子树，进而得到整个树。

/**利用vector引用的方式，可以避免每次复制导致空间利用过大，利用引用直接在原始空间内进行操作。</span>
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* getTree(vector<int> &preorder, vector<int> &inorder, int prebeg, int preend, int inbeg, int inend)
    {
        if(prebeg < preend && inbeg < inend)
        {
            TreeNode *rev = new TreeNode(preorder[prebeg]);
            vector<int>::iterator mid = find(inorder.begin()+inbeg, inorder.begin()+inend, preorder[prebeg]);
            int span = mid - (inorder.begin() + inbeg);
            rev->left = getTree(preorder, inorder, prebeg+1, prebeg+1+span, inbeg, inbeg+span);
            rev->right = getTree(preorder, inorder, prebeg+1+span, preend, inbeg+span+1, inend);
            return rev;
        }
        return NULL;
    }
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return getTree(preorder, inorder, 0, preorder.size(), 0, inorder.size());
    }
};

后+中：

与上述类似，只不对后序，根节点在末尾，其它的可依此类推。

/**利用vector引用的方式，可以避免每次复制导致空间利用过大，利用引用直接在原始空间内进行操作。</span>
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *getTree(vector<int> &inorder, vector<int> &postorder, int inbeg, int inend, int postbeg, int postend)
    {
        if (inbeg < inend && postbeg < postend)
        {
            TreeNode *rev =new TreeNode(postorder[postend-1]);
            vector<int>::iterator mid = find(inorder.begin()+inbeg, inorder.begin()+inend, postorder[postend-1]);
            int span = mid - (inorder.begin() + inbeg);
            rev->left = getTree(inorder, postorder, inbeg, inbeg+span, postbeg, postbeg+span);
            rev->right = getTree(inorder, postorder, inbeg+span+1, inend, postbeg+span, postend-1);
            return rev;
        }
        return NULL;
    }
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        return getTree(inorder, postorder, 0, inorder.size(), 0, postorder.size());
    }
};

先+后：

这种情况下恢复的二叉树不一定有唯一解，考虑如下的树：

         1

       /

    2

先序：1,2

后序：2,1

与

 1

       \

           2

先序: 1,2

后序：2,1

可看到不同的树，先，后序遍历是一样的。

其唯一解的条件文章开头已经说过了。不过没有经过严格考究！

这里只针对有唯一解的情况做讨论，还考虑上图的例子，结合实例描述如下：

先序：1,2,4,5,10,11,3,6,7,

后序：4,10,11,5,2,6,7,3,1,

对先序，第一个节点与后序最后节点对应，然后再看先序的第二个节点（值为2），我们知道，如果先序存在子树，则必同时存在左右子树，因此可断定，第二个节点正是根节点的左子树节点，可先恢复成：

           1

       /

  2

而它又把后序分成两个部分，一左一右（右边不包括最末的根节点）：左（4,10,11,5,2），右（6,7,3），说到这里，再结合上图，一切都明白了：“左”正是根的左子树，“右”正是根的右子树。于是，我们又得到了根节点的左右子树，递归，搞定。

上代码：