设计君网站,博客社区类网站模板,网站模板 瀑布流,海淀企业网站建设从前序与中序遍历序列构造二叉树 先序无法确定子树大小#xff0c;中序找不到根#xff1b;所以用先序找根#xff0c;用中序找大小题解1 递归题解2 迭代 给定两个整数数组
preorder 和
inorder #xff0c;其中
preorder 是二叉树的先序遍历#xff0c;
inorder 是同… 从前序与中序遍历序列构造二叉树 先序无法确定子树大小中序找不到根所以用先序找根用中序找大小题解1 递归题解2 迭代 给定两个整数数组
preorder 和
inorder 其中
preorder 是二叉树的先序遍历
inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 先序无法确定子树大小中序找不到根所以用先序找根用中序找大小
题解1 递归
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {unordered_mapint, int idx;
public:
// 先序自上而下中序确定左右子树大小TreeNode* build(vectorint preorder, vectorint inorder, int pre_left, int pre_right, int in_left, int in_right){if(pre_left pre_right) return nullptr;// 用前序找根把树单元化叶子结点看作无左右子的根 中序找左树大小int root_idx pre_left;// 哈希表查此根结点在中序遍历数组的位置int root_in idx[preorder[root_idx]];TreeNode* root new TreeNode(preorder[root_idx]);// 左树大小int num_left root_in - in_left;// left树越往下走右边界越收紧// 但在preoreder里涉及到赋值需要往后找左边界1root-left build(preorder, inorder, pre_left1, pre_leftnum_left, in_left, root_in-1);// right树越往下走左边界约收紧// 同样在preorder里涉及到遍历问题先序遍历遍历完左再遍历右所以到右侧应该是num_left1// 再inorder里就是在根节点的右侧root_in1即可root-right build(preorder, inorder, pre_leftnum_left1, pre_right, root_in1, in_right);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int s preorder.size();for(int i 0; i s; i){idx[inorder[i]] i;}// 含右边界的版本return build(preorder, inorder, 0, s-1, 0, s-1);}
};题解2 迭代
class Solution {unordered_mapint, int idx;
public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {int s preorder.size();TreeNode* root new TreeNode(preorder[0]);stackTreeNode* rstk;rstk.push(root);int idx 0;for(int i 1; i s; i){int val preorder[i];TreeNode* node rstk.top();// 判断当前node是不是叶子结点(拐点)if(node-val ! inorder[idx]){node-left new TreeNode(val);rstk.push(node-left);}else{// 用中序查当前先序的结点i是不是右树while(rstk.size() rstk.top()-val inorder[idx]){node rstk.top();rstk.pop();idx ;}node-right new TreeNode(val);rstk.push(node-right);}}return root;}
};
