点击刷新
思路：
labuladong手把手带你刷二叉树（第二期）
按照题目给出的例子，输入的数组为[3,2,1,6,0,5]，对于整棵树的根节点来说，其实在做这件事：
TreeNode constructMaximumBinaryTree([3,2,1,6,0,5]) { // 找到数组中的最大值 TreeNode root = new TreeNode(6); // 递归调用构造左右子树 root.left = constructMaximumBinaryTree([3,2,1]); root.right = constructMaximumBinaryTree([0,5]); return root; }
也就是找到数组中的最大值，创建root，然后分别递归左右部分
class Solution { public: TreeNode* constructMaximumBinaryTree(vector<int>& nums) { return build(nums,0,nums.size()-1); } TreeNode* build(vector<int>& nums, int lo,int hi) { if(lo>hi) return NULL; int index=lo; int max=nums[lo]; for(int i=lo;i<=hi;++i){ if(nums[i]>max){ index=i; max=nums[i]; } } TreeNode* root=new TreeNode(max); root->left=build(nums,lo,index-1); root->right=build(nums,index+1,hi); return root; } };
[105] 从前序与中序遍历序列构造二叉树
思路：
前序遍历保证了preorder[0]就是根节点，然后可以根据根节点在inorder中找到对应位置，以此来确定左子树的长度和右子树的长度，返回到preorder中划分开左右子树。
class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { TreeNode* node=sol(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1); return node; } TreeNode* sol(vector<int>& preorder, int pl,int pr, vector<int>& inorder,int il,int ir) { if(pl>pr||il>ir) return NULL; int val=preorder[pl]; int index=0; for(int i=il;i<=ir;++i){ if(inorder[i]==val){ index=i; } } int left_len = index-il; int right_len = ir-index; TreeNode* root = new TreeNode(val); root->left=sol(preorder,pl+1,pl+left_len,inorder,il,index-1); root->right=sol(preorder,pl+left_len+1,pr,inorder,index+1,ir); return root; } };
[106] 从中序与后序遍历序列构造二叉树
思路：
同上，后序遍历保证最后一位是根节点，然后到中序遍历中找到左右子树长度
class Solution { public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { TreeNode* res=sol(inorder,0,inorder.size()-1, postorder,0,postorder.size()-1); return res; } TreeNode *sol(vector<int>& inorder, int il,int ir, vector<int>& postorder,int pl,int pr) { if(il>ir||pl>pr) return NULL; int root=postorder[pr]; int x=0; for(int i=il;i<=ir;++i) { if(root==inorder[i]) { x=i; break; } } TreeNode* node=new TreeNode(root); TreeNode* left=sol(inorder,il,x-1,postorder,pl,pl+(x-il)-1); TreeNode* right=sol(inorder,x+1,ir,postorder,pl+(x-il),pr-1); node->left=left; node->right=right; return node; } };
© 著作权归作者所有
举报
相关热门文章
发表评论
0/200
