网站建设授权书,洛阳建站推广公司,wordpress怎么添加价格和购物车,网站的公共头部怎么做文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树这两道题有些类似#xff0c;相关代… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树这两道题有些类似相关代码可以互相参考本题明示了要用递归来做那么递归三要素不可缺少输入参数和返回值单层递归逻辑终止条件。本题当中输入参数引用二叉树遍历数组同时根据最大值划分的边界[Begin, End)代码统一为左闭右开区间区间具体如何划分设计到边界条件是否1-1这种。返回值为root根节点。 程序如下
class Solution {
public:// 3、输入参数TreeNode* traversal(const vectorint nums, int Begin, int End) {// 1、终止条件if (Begin End) return NULL;//2、单层递归逻辑int maxIndex Begin;for (int i Begin; i End; i) { // 找最大值if (nums[i] nums[maxIndex]) maxIndex i;}TreeNode* root new TreeNode(nums[maxIndex]);// 最大值左边部分左闭右开[leftBegin, leftEnd)int leftBegin Begin; int leftEnd maxIndex;if (leftEnd leftBegin) leftEnd Begin;// 最大值右边部分左闭右开[rightBegin, rightEnd)int rightBegin maxIndex 1;int rightEnd End;if (rightBegin rightEnd) rightBegin End;root-left traversal(nums, leftBegin, leftEnd);root-right traversal(nums, rightBegin, rightEnd);// 3、返回值return root;}TreeNode* constructMaximumBinaryTree(vectorint nums) { if (!nums.size()) return NULL;return traversal(nums, 0, nums.size());}
};三、完整代码
# include iostream
# include vector
# include queue
using namespace std;// 树节点定义
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 {
public:// 3、输入参数TreeNode* traversal(const vectorint nums, int Begin, int End) {// 1、终止条件if (Begin End) return NULL;//2、单层递归逻辑int maxIndex Begin;for (int i Begin; i End; i) { // 找最大值if (nums[i] nums[maxIndex]) maxIndex i;}TreeNode* root new TreeNode(nums[maxIndex]);// 最大值左边部分左闭右开[leftBegin, leftEnd)int leftBegin Begin; int leftEnd maxIndex;if (leftEnd leftBegin) leftEnd Begin;// 最大值右边部分左闭右开[rightBegin, rightEnd)int rightBegin maxIndex 1;int rightEnd End;if (rightBegin rightEnd) rightBegin End;root-left traversal(nums, leftBegin, leftEnd);root-right traversal(nums, rightBegin, rightEnd);// 3、返回值return root;}TreeNode* constructMaximumBinaryTree(vectorint nums) { if (!nums.size()) return NULL;return traversal(nums, 0, nums.size());}
};// 层序遍历
vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);vectorvectorint result;while (!que.empty()) {int size que.size(); // size必须固定, que.size()是不断变化的vectorint vec;for (int i 0; i size; i) {TreeNode* node que.front();que.pop();vec.push_back(node-val);if (node-left) que.push(node-left);if (node-right) que.push(node-right);}result.push_back(vec);}return result;
}templateclass T1, class T2
void my_print2(T1 v, const string str) {cout str endl;for (class T1::iterator vit v.begin(); vit v.end(); vit) {for (class T2::iterator it (*vit).begin(); it (*vit).end(); it) {cout *it ;}cout endl;}
}int main()
{//int arr[] {3, 2, 1, 6, 0, 5};int arr[] { 3, 2, 1};vectorint nums(arr, arr sizeof(arr) / sizeof(int));Solution s;TreeNode* root s.constructMaximumBinaryTree(nums);vectorvectorint tree levelOrder(root);my_print2vectorvectorint, vectorint(tree, 目标树:);system(pause);return 0;
}end
