LeetCode 106/105 从中序和后序/前序遍历序列构造二叉树

原理：

请参考文章：数据结构笔记：二叉树的构造（根据遍历顺序构造二叉树）

先序遍历 中序遍历 后序序列组成情况,

 题目链接：力扣

递归函数声明：

TreeNode* buildTree(vector& inorder, vector& postorder);

递归出口:

(1) 当inorder为空，postorder为空，返回空

if(inorder.size()==0&&postorder.size()==0)return NULL;

 (2)当inorder和postorder中只有一个元素时，返回该元素构造的根节点

if(inorder.size()==1&&postorder.size()==1)
{
  TreeNode *root=new TreeNode(inorder[0]);
  return root; 
}

递归体：

（1）后序遍历序列的最后一个元素构造二叉树根节点

（2）在中序遍历序列中找到这个根节点

        用中序序列中根节点的左部分元素递归构造二叉树的左子树

        用中序序列中根节点的右部分元素递归构造二叉树的右子树

（3）构造出整个树

完整代码：

class Solution {
public:
    TreeNode* buildTree(vector& inorder, vector& postorder) {


if(inorder.size()==0&&postorder.size()==0)return NULL;
if(inorder.size()==1&&postorder.size()==1)
{
  TreeNode *root=new TreeNode(inorder[0]);
  return root; 
}


TreeNode *root=new TreeNode(postorder[postorder.size()-1]);

//找到根节点在中序遍历序列的索引，就可以知道左子树的节点个数，右子树节点个数
int index=find(inorder.begin(),inorder.end(),postorder[postorder.size()-1])-inorder.begin();//index是根节点所在索引

vectorinorder_left(inorder.begin(),inorder.begin()+index);
vectorinorder_right(inorder.begin()+index+1,inorder.end());

vectorpostorder_left(postorder.begin(),postorder.begin()+index);
vectorpostorder_right(postorder.begin()+index,postorder.end()-1);

TreeNode *l=buildTree(inorder_left,postorder_left);
TreeNode *r=buildTree(inorder_right,postorder_right);

root->left=l;
root->right=r;

return root;    }
};

思路相同

代码

class Solution {
public:
    TreeNode* buildTree(vector& preorder, vector& inorder) {
if(inorder.size()==0&&preorder.size()==0)return NULL;
if(inorder.size()==1&&preorder.size()==1)
{
  TreeNode *root=new TreeNode(inorder[0]);
  return root; 
}


TreeNode *root=new TreeNode(preorder[0]);

//找到根节点在中序遍历序列的索引，就可以知道左子树的节点个数，右子树节点个数
int index=find(inorder.begin(),inorder.end(),preorder[0])-inorder.begin();//index是根节点所在索引

vectorinorder_left(inorder.begin(),inorder.begin()+index);
vectorinorder_right(inorder.begin()+index+1,inorder.end());

vectorpreorder_left(preorder.begin()+1,preorder.begin()+index+1);
vectorpreorder_right(preorder.begin()+index+1,preorder.end());

TreeNode *l=buildTree(preorder_left,inorder_left);
TreeNode *r=buildTree(preorder_right,inorder_right);

root->left=l;
root->right=r;

return root;  
    }
};