pa66用途障车做网站,怎么做同城购物网站,合肥做网站cnfg,安阳网红从中序与后序遍历序列构造二叉树 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如#xff0c;给出 中序遍历 inorder [9,3,15,20,7]
后序遍历 postorder [9,15,7,20,3] 返回如下的二叉树#xff1a; 3/ \9 20/ \15 7 思路… 从中序与后序遍历序列构造二叉树 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如给出 中序遍历 inorder [9,3,15,20,7]
后序遍历 postorder [9,15,7,20,3] 返回如下的二叉树 3/ \9 20/ \15 7 思路 根据构造二叉树的流程中序遍历的访问顺序为左-中-右后序遍历的方位顺序为左-右-中。 后序最后一个节点为根节点在中序列表中查找根节点值将中序列表分割成左子树中序列表和右子树中序列表因为对于同样的树中序和后序列表长度相同所以根据左子树中序列表和右子树中序列表的长度将后序列表分割成左子树后序和右子树后序对左子树根节点右子树根节点递归调用返回根节点TreeNode* buildTree(vectorint inorder, vectorint postorder)
{int ninorder.size();if(n0){TreeNode* rootnew TreeNode(postorder[n-1]);vectorint::iterator itfind(inorder.begin(),inorder.end(),postorder[n-1]);vectorint il,ir,pl,pr;il.assign(inorder.begin(),it);ir.assign(it1,inorder.end());int l,r;lil.size();rir.size();//中序后序遍历长度相等pl.assign(postorder.begin(),postorder.begin()l);pr.assign(postorder.begin()l,postorder.end());root-leftbuildTree(il,pl);root-rightbuildTree(ir,pr);return root;}else return NULL;
} 从前序与中序遍历序列构造二叉树 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如给出 前序遍历 preorder [3,9,20,15,7]
中序遍历 inorder [9,3,15,20,7] 返回如下的二叉树 3/ \9 20/ \15 7 思路 和中序后序构造思路基本一致 根据构造二叉树的流程前序遍历的访问顺序为中-左-右中序遍历的访问顺序为左-中-右。 前序第一一个节点为根节点在中序列表中查找根节点值将中序列表分割成左子树中序列表和右子树中序列表因为对于同样的树中序和前序列表长度相同所以根据左子树中序列表和右子树中序列表的长度将前序列表分割成左子树前序和右子树前序对左子树根节点右子树根节点递归调用返回根节点TreeNode* buildTree(vectorint preorder, vectorint inorder)
{int npreorder.size();if(n0){TreeNode* rootnew TreeNode(preorder[0]);vectorint::iterator itfind(inorder.begin(),inorder.end(),preorder[0]);vectorint il,ir,pl,pr;il.assign(inorder.begin(),it);ir.assign(it1,inorder.end());int l,r;lil.size();rir.size();//中序前序遍历长度相等pl.assign(preorder.begin()1,preorder.begin()l1);pr.assign(preorder.begin()l1,preorder.end());root-leftbuildTree(pl,il);root-rightbuildTree(pr,ir);return root;}else return NULL;
} 转载于:https://www.cnblogs.com/wendyy/p/9332633.html
