leetcode 106. 从中序与后序遍历序列构造二叉树 105. 从前序与中序遍历序列构造二叉树思考分析

目录

1、106题目

2、参考思路：递归切割数组

代码参考：公众号：代码随想录
后序数组+中序数组
以 后序数组(左右中)的最后一个元素作为切割点，先切中序数组，根据中序数组反过来再切割后序数组。一层一层切割下去，每次后序数组最后一个元素就是结点元素。
先序数组+中序数组
以 先序数组(中左右)的第一个元素作为切割点，先切中序数组，根据中序数组反过来再切割先序数组。一层一层切割下去，每次先序数组第一个元素就是结点元素。
先序数组+后序数组为何不能构造一个唯一的二叉树
对于一个二叉树，并不是说给出了先序和后序就是无法唯一确定的。只是说，在某些情况下，不能唯一确定。
即：

当二叉树中某个节点仅仅只有一个孩子节点的时候，就无法根据其先序和后序唯一的确定一个二叉树。
更详细的解释请看这个链接:
关于二叉树先序遍历和后序遍历为什么不能唯一确定一个二叉树分析
我的理解：由于中序遍历的存在，你只需要找到中间结点就可以十分迅速并且准确地确定它的左右孩子，而后序、前序遍历则没有这个特征。
举例：给定序列1 2 3 4，且中间结点是3。
中序遍历，则可得到：1、2是3结点的左子树的结点、4是3结点的右子树的结点
给定序列1 2 3 4，且中间结点是1。
先序遍历，你不知道234三个结点究竟是怎样分布在左右子树上的，可能是：
【234】【】；
【23】【4】；
【2】【34】；
【】【234】；
后序遍历同理。

递归分析：

1、如果数组大小为0的话，说明就是空结点。
2、如果不为空，那么取后序数组最后一个元素作为结点元素
3、找到后序数组最后一个元素在中序数组的位置，作为切割点
4、切割中序数组，切割成中序左数组和中序右数组
5、切割后序数组，切成后序左数组和后序右数组
6、递归处理左区间和右区间

关于构造二叉树的方法，回顾;
LintCode 375. 克隆二叉树(深复制)

TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
       //step1
       if(postorder.size() == 0 ) return NULL;
       //step2:后序遍历数组的最后一个元素就是当前的中间结点
       int rootVal = postorder[postorder.size()-1];
       TreeNode* NewRoot = new TreeNode(rootVal);
       //如果是叶子结点，返回结点
       if(postorder.size() == 1) return NewRoot;
       //step3：寻找切割点
       int CutIndex ;
       for(CutIndex=0;CutIndex<inorder.size();CutIndex++)
       {
           if(inorder[CutIndex] == rootVal) break;
       }
       //step4:切割中序数组，得到中序左数组和中序右数组
       //step5:切割后序数组，得到后序左数组和后序右数组
       //step6：
       /*
       root->left = traversal(中序左数组,后序左数组);
       root->left = traversal(中序右数组,后序右数组);
       */
    }

切割的原则我们遵循左闭右开(右边的不取).
切割中序数组

//找到中序遍历的切割点
int CutIndex ;
for(CutIndex=0;CutIndex<inorder.size();CutIndex++)
{
    if(inorder[CutIndex] == rootVal) break;
}
//区间形式：[x1,x2);
vector<int> leftInorder(inorder.begin(),inorder.begin()+CutIndex );
vector<int> rightInorder(inorder.begin()+CutIndex+1,inorder.end() );

切割后序数组
1、后序数组没有明确的切割元素来进行左右切割。
2、中序数组的大小和后序数组的大小相同。
3、我们已经将中序数组切割成了左、右两个子数组了。
4、舍弃掉后序数组末尾元素，因为这个元素是中间结点

//舍弃末尾元素
postorder.resize(postorder.size() -1 );
//左闭右开，使用了左中序数组大小作为切割点：[0,leftorder.size()]
vector<int> leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size());
vector<int> rightPostorder(postorder.begin()+leftInorder.size(),postorder.end());

接下来是递归

root->left = traversal(leftInorder,leftPostorder);
root->right= traversal(rightInorder,rightPostorder);

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
       //step1
       if(postorder.size() == 0 ) return NULL;
       //step2:后序遍历数组的最后一个元素就是当前的中间结点
       int rootVal = postorder[postorder.size()-1];
       TreeNode* NewRoot = new TreeNode(rootVal);
       //如果是叶子结点，返回结点
       if(postorder.size() == 1) return NewRoot;
       //step3：寻找切割点
       int CutIndex ;
       for(CutIndex=0;CutIndex<inorder.size();CutIndex++)
       {
           if(inorder[CutIndex] == rootVal) break;
       }
       //step4:切割中序数组，得到中序左数组和中序右数组
       //区间形式：[x1,x2);
       vector<int> leftInorder(inorder.begin(),inorder.begin()+CutIndex );
       vector<int> rightInorder(inorder.begin()+CutIndex+1,inorder.end() );
       //step5:切割后序数组，得到后序左数组和后序右数组
       //舍弃末尾元素
       postorder.resize(postorder.size() -1 );
       //左闭右开，使用了左中序数组大小作为切割点：[0,leftorder.size()]
       vector<int> leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size());
       vector<int> rightPostorder(postorder.begin()+leftInorder.size(),postorder.end());
       //step6：
       NewRoot->left = traversal(leftInorder,leftPostorder);
       NewRoot->right= traversal(rightInorder,rightPostorder);
       return NewRoot;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder,postorder);
    }
};

分析：每层递归都定义了数组，耗时间也耗空间。
下面给出用下标索引分割代码，不需要重新构造数组了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
// 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)
    TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
        if (postorderBegin == postorderEnd) return NULL;

        int rootValue = postorder[postorderEnd - 1];
        TreeNode* root = new TreeNode(rootValue);

        if (postorderEnd - postorderBegin == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 切割中序数组
        // 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割后序数组
        // 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
        int leftPostorderBegin =  postorderBegin;
        int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
        // 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
        int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
        int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  postorder, leftPostorderBegin, leftPostorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);

        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder,0,inorder.size(),postorder,0,postorder.size());
    }
};

3、105题目

4、同样思路的代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
// 中序区间：[inorderBegin, inorderEnd)，先序区间[preorderBegin, preorderEnd)
    TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) {
        if (preorderBegin == preorderEnd) return NULL;

        int rootValue = preorder[preorderBegin];
        TreeNode* root = new TreeNode(rootValue);

        if (preorderEnd - preorderBegin == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 切割中序数组
        // 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割先序数组
        // 左先序区间，左闭右开[leftPreorderBegin, leftPreorderEnd)
        int leftPreorderBegin =  preorderBegin + 1;// 排除第一个元素，已经作为节点了
        int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
        // 右先序区间，左闭右开[rightPreorderBegin, rightPreorderEnd)
        int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);
        int rightPreorderEnd = preorderEnd;  

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  preorder, leftPreorderBegin, leftPreorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);

        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
         if(inorder.size() == 0 || preorder.size() == 0) return NULL;
        return traversal(inorder,0,inorder.size(),preorder,0,preorder.size());
    }
};