手机网站打不开是什么原因造成的,上海营销型网站标准,长沙可以做网站的公司,免费发布网站文章目录 一、最大的二叉树二、合并二叉树三、二叉搜索树中的搜索四、验证二叉搜索树 一、最大的二叉树
654.最大的二叉树 构建二叉树的题目#xff0c;都用前序遍历。 因为我们一定要先构建根节点#xff0c;才能继续向后构建。
递归函数的参数和返回值#xff1a;
Tree… 文章目录 一、最大的二叉树二、合并二叉树三、二叉搜索树中的搜索四、验证二叉搜索树 一、最大的二叉树
654.最大的二叉树 构建二叉树的题目都用前序遍历。 因为我们一定要先构建根节点才能继续向后构建。
递归函数的参数和返回值
TreeNode* constructMaximumBinaryTree(vectorint nums) {}终止条件
if (nums.size() 1)return new TreeNode(nums[0]);单层递归逻辑
TreeNode *node new TreeNode(maxVal);
if (maxValueIndex 0)
{vectorint newVec(nums.begin(), nums.begin() maxValueIndex);node-left constructMaximumBinaryTree(newVec);
}
if (maxValueIndex nums.size() - 1)
{vectorint newVec(nums.begin() maxValueIndex 1, nums.end());node-right constructMaximumBinaryTree(newVec);
}
return node;完整代码 class Solution
{
public:TreeNode *constructMaximumBinaryTree(vectorint nums){if (nums.size() 1)return new TreeNode(nums[0]);// 单层递归// 找到数组中最大的值和对应的下标
中 int maxVal 0;int maxValueIndex 0; // 最大值所在下标 为啥要存下标呢 因为下层递归分割的时候需要使用下标来分割数组for (int i 0; i nums.size(); i){if (nums[i] maxVal){maxVal nums[i];maxValueIndex i;}}TreeNode *node new TreeNode(maxVal);
左 if (maxValueIndex 0){vectorint newVec(nums.begin(), nums.begin() maxValueIndex);node-left constructMaximumBinaryTree(newVec);}
右 if (maxValueIndex nums.size() - 1){vectorint newVec(nums.begin() maxValueIndex 1, nums.end());node-right constructMaximumBinaryTree(newVec);}return node;}
};为啥会有两个判断 if (maxValueIndex 0) if (maxValueIndex nums.size() - 1) 因为要保证划分的左右区间至少都有一个值。
二、合并二叉树
617.合并二叉树 使用前序是最容易理解的。
class Solution
{
public:TreeNode *mergeTrees(TreeNode *t1, TreeNode *t2){if (t1 nullptr)return t2;if (t2 nullptr)return t1;// 单层递归逻辑// 复用 t1 的结构t1-val t2-val;t1-left mergeTrees(t1-left, t2-left);t1-right mergeTrees(t1-right, t2-right);return t1;}
};三、二叉搜索树中的搜索
700.二叉搜索树中的搜索 利用二叉搜索树的性质。(根的值大于左子树小于右子树)
class Solution
{
public:TreeNode *searchBST(TreeNode *root, int val){if (root nullptr)return nullptr;if (root-val val)return root;// 单层递归逻辑TreeNode *res;// 若子树中出现了目标值那么我们需要一个变量来返回我们的节点if (val root-val)res searchBST(root-left, val);if (val root-val)res searchBST(root-right, val);return res;}
};四、验证二叉搜索树
98.验证二叉搜索树 我们遇到二叉搜索树中搜索类的题目大概率是需要用到中序遍历的。
最为简单和直观的一种解法
class Solution
{
public:vectorint v;void inorder(TreeNode *root){if (root nullptr)return;inorder(root-left);v.push_back(root-val);inorder(root-right);}bool isValidBST(TreeNode *root){// 把中序遍历的结果放入vector中遍历这个vector看它是否是升序的inorder(root);for (int i 1; i v.size(); i){if (v[i] v[i - 1]){continue;}else{return false;}}return true;}
};定义一个pre来帮助比较
class Solution
{
public:TreeNode *pre nullptr;bool isValidBST(TreeNode *root){if (root nullptr)return true;// 单层递归逻辑bool left isValidBST(root-left);if (pre ! nullptr pre-val root-val)return false;pre root;// 记录前一个节点每次递归都要更新prebool right isValidBST(root-right);return left right;}
};
