654. 最大二叉树
难度中等196收藏分享切换为英文接收动态反馈
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。通过给定的数组构建最大二叉树，并且输出这个树的根节点。
示例 ：
输入：[3,2,1,6,0,5] 输出：返回下面这棵树的根节点： 6 / \ 3 5 \ / 2 0 \ 1
提示：
给定的数组的大小在 [1, 1000] 之间。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* constructMaximumBinaryTree(vector<int>& nums) { return maxTree(nums, 0, nums.size()-1); } TreeNode* maxTree(vector<int>&nums,int left,int right) { //如果左端的下标值大于右端，则说明该节点为空 if(left>right) return NULL; //左端等于右端则直接构造叶子节点 if(left==right) { return new TreeNode(nums[left]); } int rootIndex=left; //寻找最大值的节点并对rootIndex赋值 for(int i=left+1;i<=right;i++) { if(nums[i]>nums[rootIndex]) { rootIndex=i; } } TreeNode* root=new TreeNode(nums[rootIndex]); //左子树的下边范围左端不变，右端是根节点的前面一个 root->left=maxTree(nums,left,rootIndex-1); //右子树的下标范围右端不变，左端是根节点的后面一个 root->right=maxTree(nums,rootIndex+1,right); return root; } };
105. 从前序与中序遍历序列构造二叉树
难度中等703收藏分享切换为英文接收动态反馈
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：
3 / \ 9 20 / \ 15 7通过次数119,209提交次数174,776
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if(preorder.size()==0 || inorder.size()==0) return NULL; return build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1); } TreeNode* build(vector<int>& preorder,int ps,int pe,vector<int>& inorder,int is,int ie) { //构建根节点 TreeNode* root = new TreeNode(preorder[ps]); root->left = NULL; root->right = NULL; //在中序序列中寻找根节点 int i = is; while(i<=ie&&preorder[ps]!=inorder[i]) ++i; //i 指向中序遍历中根节点位置 int l1 = i-is; //左子树的序列长度 int r1 = ie-i;//右子树的序列长度 if(l1>0) root->left = build(preorder,ps+1,ps+l1,inorder,is, is+l1-1); if(r1>0) root->right = build(preorder,ps+l1+1,pe,inorder,is+l1+1,ie); return root; } };
106. 从中序与后序遍历序列构造二叉树
难度中等381收藏分享切换为英文接收动态反馈
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]返回如下的二叉树：
3 / \ 9 20 / \ 15 7通过次数72,219提交次数102,200
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { private: TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) { if (postorder.size() == 0) return NULL; // 后序遍历数组最后一个元素，就是当前的中间节点 int rootValue = postorder[postorder.size() - 1]; TreeNode* root = new TreeNode(rootValue); // 叶子节点 if (postorder.size() == 1) return root; // 找到中序遍历的切割点 int delimiterIndex; for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) { if (inorder[delimiterIndex] == rootValue) break; } // 切割中序数组 // 左闭右开区间：[0, delimiterIndex) vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex); // [delimiterIndex + 1, end) vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() ); // postorder 舍弃末尾元素 postorder.resize(postorder.size() - 1); // 切割后序数组 // 依然左闭右开，注意这里使用了左中序数组大小作为切割点 // [0, leftInorder.size) vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size()); // [leftInorder.size(), end) vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end()); root->left = traversal(leftInorder, leftPostorder); root->right = traversal(rightInorder, rightPostorder); return root; } public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if (inorder.size() == 0 || postorder.size() == 0) return NULL; return traversal(inorder, postorder); } };
