做网站需要买,手机网站建设免费,招商网网站建设方案,外国人做的网站由前/中/后遍历序列构建二叉树
基础
首先#xff0c;我们需要知道前中后序三种深度优先遍历二叉树的方式的具体顺序#xff1a;
前序#xff1a;中左右中序#xff1a;左中右后序#xff1a;左右中
另外#xff0c;要知道只有中序前/后序可以唯一确定一棵二叉树…由前/中/后遍历序列构建二叉树
基础
首先我们需要知道前中后序三种深度优先遍历二叉树的方式的具体顺序
前序中左右中序左中右后序左右中
另外要知道只有中序前/后序可以唯一确定一棵二叉树而前序后序是不能唯一确定一棵二叉树的。
思路
在构造二叉树的题目中我们通常是采用递归形式的分治思想来实现。在前/后序列中我们知道其最前/最后的元素一定是根结点我们将根结点的值取出来并在中序序列中找到该节点的值此类题目通常保证遍历序列中无重复元素并记下其索引。
在中序序列中根结点左右的序列就分别是其左右子树的中序序列我们再递归地构造其左右子树最终得到完整的树。
105. 从前序与中序遍历序列构造二叉树
看一下前序和中序有什么特点前序1,2,4,7,3,5,6,8 中序4,7,2,1,5,3,8,6
当前要构造的树可能是整体的某个子树所需的前序/中序遍历序列肯定是整体所求树的前序/中序遍历序列的某个子序列我们用 preLeft, preRight, inLeft, inRight 分别表示该子序列在整体前序/中序序列中的起始位置。
前序中左起第一位1肯定是根结点 root我们可以根据其值 rootVal 找到中序中根结点的位置记为 mid中序中根结点左边就是左子树结点右边就是右子树结点。即[左子树结点根结点右子树结点]我们就可以得出左子树结点个数为 mid-inLeft前序中结点分布应该是[根结点左子树结点右子树结点]根据前一步确定的左子树个数可以确定前序中左子树结点和右子树结点的范围如果我们要前序遍历生成二叉树的话下一层递归应该是 左子树root-left helper(preorder, inorder, 左子树前序起始点, 左子树前序终止点, 左子树中序起始点, 左子树中序终止点);右子树root-right helper(preorder, inorder, 右子树前序起始点, 右子树前序终止点, 右子树中序起始点, 右子树中序终止点); 每一层递归都要返回当前根结点root 全部代码如下
class Solution {
private:TreeNode* helper(vectorint preorder, vectorint inorder, int preLeft, int preRight, int inLeft, int inRight) {if (inLeft inRight) return nullptr;int rootVal preorder[preLeft];int mid inLeft;for (; midinRight; mid) if (inorder[mid] rootVal) break;TreeNode* root new TreeNode(rootVal);root-left helper(preorder, inorder, preLeft1, preLeft1mid-inLeft, inLeft, mid);root-right helper(preorder, inorder, preLeft1mid-inLeft, preRight, mid1, inRight);return root;}
public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {return helper(preorder, inorder, 0, preorder.size(), 0, inorder.size());}
};106. 从中序与后序遍历序列构造二叉树
与前序中序构造二叉树类似
class Solution {
private:TreeNode* helper(vectorint inorder, vectorint postorder, int inLeft, int inRight, int postLeft, int postRight) {if (inLeft inRight) return nullptr;int rootVal postorder[postRight-1];int mid inLeft;for (; midinRight; mid) if (inorder[mid] rootVal) break;TreeNode* root new TreeNode(rootVal);root-left helper(inorder, postorder, inLeft, mid, postLeft, postLeftmid-inLeft);root-right helper(inorder, postorder, mid1, inRight, postLeftmid-inLeft, postRight-1);return root;}
public:TreeNode* buildTree(vectorint inorder, vectorint postorder) {return helper(inorder, postorder, 0, inorder.size(), 0, postorder.size());}
};889. 根据前序和后序遍历构造二叉树
注意我们之前提到前序/后序序列并不能唯一确定一棵二叉树实际上只有每个节点度为2或者0的时候前序和后序才能唯一确定一颗二叉树所以本题题目说明中有 每个输入保证至少有一个答案。如果有多个答案可以返回其中一个。 class Solution {
private:TreeNode* helper(vectorint preorder, vectorint postorder, int preLeft, int preRight, int postLeft, int postRight) {if (preLeft preRight) return nullptr;int rootVal preorder[preLeft];TreeNode* root new TreeNode(rootVal);if (preLeft preRight) return root;int mid 0;for (; midpostRight; mid) if (postorder[mid] preorder[preLeft1]) break;root-left helper(preorder, postorder, preLeft1, preLeft1mid-postLeft, postLeft, mid);root-right helper(preorder, postorder, preLeft2mid-postLeft, preRight, mid1, postRight-1);return root;}
public:TreeNode* constructFromPrePost(vectorint preorder, vectorint postorder) {return helper(preorder, postorder, 0, preorder.size()-1, 0, postorder.size()-1);}
};
