1.问题描述:来自学习总结
2.思路根据一棵树的中序遍历与后序遍历构造二叉树(假设树中没有重复的元素)
中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树:
以后序数组的最后一个元素为切割点,先切中序数组,根据中序数组,反过来切后序数组,一层一层切下去,每次后续数组最后一个元素就是节点元素
一层一层切割的步骤:(递归)
- 如果数组大小为0,说明是空节点
- 若不为空,name去后序数组最后一个元素作为节点元素
- 找到后序数组最后一个元素在中序数组的位置,作为切割点
- 切割中序数组,切成中序左数组和中序右数组
- 切割后续数组,切成后续数组和后序数组
- 递归处理左区间和右区间
4.代码实现
public TreeNode* traversal(vector& inorder,vector & postorder){ //1. if(postorder.size()==0) return null; //2.后续遍历的最后一个元素,就是当前的节点 int rootVal=postorder[postorder.size()-1]; TreeNode* root=new TreeNode(rootVal); //叶子结点 if(postorder.size()==1) return root; //3.切割点 int delimiterIndex; for(delimiterIndex=0;delimiterIndex if(inorder[delimiterIndex]==rootVal) break; } //4切割中序数组 //左闭右开区间[0,delimiterIndex) vector leftInorder(inorder.begin(),inorder.begin()+delimiterIndex); //[delimiterIndex+1,end) vector rightInorder(inorder.begin()+delimiterIndex+1,index.end()); //舍弃末尾元素 postorder.resize(postorder.size()-1); //5切割后序数组 //左闭右开,注意这里使用了左中序数组大小作为切割点[0,leftorder.size) vector leftPostOrder(postorder.begin(),postorder.begin()+leftInorder.size()); //[leftInorder.size(),end) vector rightPostorder(postorder.begin()+leftInorder.size(),postorder.end()); //6. root->left=traversal(); root->right=traversal(); return root; }