LeetCode 中级 - 从前序与中序遍历序列构造二叉树(105)

一个前序遍历序列和一个中序遍历序列可以确定一颗唯一的二叉树。

       根据前序遍历的特点, 知前序序列(PreSequence)的首个元素(PreSequence[0])为二叉树的根(root),  然后在中序序列(InSequence)中查找此根(root),  根据中序遍历特点, 知在查找到的根(root) 前边的序列为根的左子树的中序遍历序列,  后边的序列为根的右子树的中序遍历序列。 设在中序遍历序列(InSequence)根前边有left个元素. 则在前序序列(PreSequence)中, 紧跟着根(root)的left个元素序列(即PreSequence[1...left]) 为根的左子树的前序遍历序列, 在后边的为根的右子树的前序遍历序列.而构造左子树问题其实跟构造整个二叉树问题一样，只是此时前序序列为PreSequence[1...left]), 中序序列为InSequence[0...left-1], 分别为原序列的子串, 构造右子树同样, 显然可以用递归方法解决。
原文：https://blog.csdn.net/yunzhongguwu005/article/details/9270085

/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
     if(preorder.size()==0||inorder.structize()==0)
         return NULL;
    else
    {
        return buildCore(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);        
      }
}
    TreeNode *buildCore(vector<int>&preorder,int preSt,int preEnd,vector<int>&inorder,int inSt,int inEnd)
    {
        //前序遍历的第一个节点是根节点root
        int rootValue=preorder[preSt];
        TreeNode *root=new TreeNode(rootValue);
        
        //前序序列只有根节点时
        if(preSt==preEnd)
            return root;
        
        //遍历中序序列找到根节点的位置
        int rootInorder = inSt;
        while(inorder[rootInorder]!=rootValue&&rootInorder<=inEnd)
            rootInorder++;

        //计算左子树的长度
        int leftLength=rootInorder-inSt;
        //前序序列中左子数的最后一个节点
        int leftPreEnd=preSt+leftLength;
        
        //左子树非空
        if(leftLength>0)
        {
            //重建左子树
            root->left=buildCore(preorder,preSt+1,leftPreEnd,inorder,inSt,rootInorder-1);
        }   
        //右子树非空
        if(leftLength<preEnd-preSt)
        {
            //重建右子树
            root->right=buildCore(preorder,leftPreEnd+1,preEnd,inorder,rootInorder+1,inEnd);
        }
        return root;
    }
};

从中序与后序遍历序列构造二叉树 ，和第一种类似...。

/**
 * 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* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size()==0||postorder.size()==0)
            return NULL;
        else 
            return buildCoreTree(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
    }
    
    TreeNode *buildCoreTree(vector<int>&inorder,int inSt,int inEnd,vector<int>&postorder,int postSt,int postEnd)
    {
        int rootValue=postorder[postEnd];
        TreeNode *root=new TreeNode(rootValue);
        if(postEnd==postSt)
            return root;
        
        int rootInorder=inSt;
        while(inorder[rootInorder]!=rootValue&&rootInorder<=inEnd)
            rootInorder++;
        
        int leftLength=rootInorder-inSt;
        int leftPostEnd=postSt+leftLength;
        if(leftLength>0)
        {
            root->left=buildCoreTree(inorder,inSt,rootInorder-1,postorder,postSt,leftPostEnd-1);
        }
        if(leftLength<inEnd-inSt)
        {
            root->right=buildCoreTree(inorder,rootInorder+1,inEnd,postorder,leftPostEnd,postEnd-1);
        }
        return root;
    }
};