重庆网站建设seo优化,公司网站域名续费一年多少钱,培训机构课程设置,网站建设 麦肯趋势day20 654.最大二叉树617.合并二叉树700.二叉搜索树中的搜索98.验证二叉搜索树 654.最大二叉树
题目链接 解题思路#xff1a; 本题属于构造二叉树#xff0c;需要使用前序遍历#xff0c;因为先构造中间节点#xff0c;然后递归构造左子树和右子树。
确定递归函数的参数… day20 654.最大二叉树617.合并二叉树700.二叉搜索树中的搜索98.验证二叉搜索树 654.最大二叉树
题目链接 解题思路 本题属于构造二叉树需要使用前序遍历因为先构造中间节点然后递归构造左子树和右子树。
确定递归函数的参数和返回值 参数传入的是存放元素的数组返回该数组构造的二叉树的头结点返回类型是指向节点的指针。 代码如下
TreeNode* constructMaximumBinaryTree(vectorint nums)确定终止条件 题目中说了输入的数组大小一定是大于等于1的所以我们不用考虑小于1的情况那么当递归遍历的时候如果传入的数组大小为1说明遍历到了叶子节点了。 那么应该定义一个新的节点并把这个数组的数值赋给新的节点然后返回这个节点。 这表示一个数组大小是1的时候构造了一个新的节点并返回。
代码如下
TreeNode* node new TreeNode(0);
if (nums.size() 1) {node-val nums[0];return node;
}确定单层递归的逻辑
这里有三步工作
先要找到数组中最大的值和对应的下标 最大的值构造根节点下标用来下一步分割数组。
代码如下
int maxValue 0;
int maxValueIndex 0;
for (int i 0; i nums.size(); i) {if (nums[i] maxValue) {maxValue nums[i];maxValueIndex i;}
}
TreeNode* node new TreeNode(0);
node-val maxValue;最大值所在的下标左区间 构造左子树
这里要判断maxValueIndex 0因为要保证左区间至少有一个数值。
代码如下
if (maxValueIndex 0) {vectorint newVec(nums.begin(), nums.begin() maxValueIndex);node-left constructMaximumBinaryTree(newVec);
}最大值所在的下标右区间 构造右子树
判断maxValueIndex (nums.size() - 1)确保右区间至少有一个数值。
代码如下
if (maxValueIndex (nums.size() - 1)) {vectorint newVec(nums.begin() maxValueIndex 1, nums.end());node-right constructMaximumBinaryTree(newVec);
}整体代码如下
class Solution {
public:TreeNode* constructMaximumBinaryTree(vectorint nums) {TreeNode* node new TreeNode(0);if (nums.size() 1) {node-val nums[0];return node;}// 找到数组中最大的值和对应的下标int maxValue 0;int maxValueIndex 0;for (int i 0; i nums.size(); i) {if (nums[i] maxValue) {maxValue nums[i];maxValueIndex i;}}node-val maxValue;// 最大值所在的下标左区间 构造左子树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;}
}; 617.合并二叉树
题目链接 解题思路 递归三部曲来解决
确定递归函数的参数和返回值
首先要合入两个二叉树那么参数至少是要传入两个二叉树的根节点返回值就是合并之后二叉树的根节点。
代码如下
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {确定终止条件
因为是传入了两个树那么就有两个树遍历的节点t1 和 t2如果t1 NULL 了两个树合并就应该是 t2 了如果t2也为NULL也无所谓合并之后就是NULL。
反过来如果t2 NULL那么两个数合并就是t1如果t1也为NULL也无所谓合并之后就是NULL。
代码如下
if (t1 NULL) return t2; // 如果t1为空合并之后就应该是t2
if (t2 NULL) return t1; // 如果t2为空合并之后就应该是t1确定单层递归的逻辑
单层递归的逻辑就比较好写了这里我们重复利用一下t1这个树t1就是合并之后树的根节点就是修改了原来树的结构。
那么单层递归中就要把两棵树的元素加到一起。
t1-val t2-val;接下来t1 的左子树是合并 t1左子树 t2左子树之后的左子树。
t1 的右子树是 合并 t1右子树 t2右子树之后的右子树。
最终t1就是合并之后的根节点。
代码如下
t1-left mergeTrees(t1-left, t2-left);
t1-right mergeTrees(t1-right, t2-right);
return t1;此时前序遍历完整代码就写出来了如下
整体代码如下
class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 NULL) return t2; // 如果t1为空合并之后就应该是t2if (t2 NULL) return t1; // 如果t2为空合并之后就应该是t1// 修改了t1的数值和结构t1-val t2-val; // 中t1-left mergeTrees(t1-left, t2-left); // 左t1-right mergeTrees(t1-right, t2-right); // 右return t1;}
};700.二叉搜索树中的搜索
题目链接 解题思路 二叉搜索树是一个有序树
若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树
1.确定递归函数的参数和返回值
递归函数的参数传入的就是根节点和要搜索的数值返回的就是以这个搜索数值所在的节点。
代码如下
TreeNode* searchBST(TreeNode* root, int val)确定终止条件
如果root为空或者找到这个数值了就返回root节点。
if (root NULL || root-val val) return root;确定单层递归的逻辑
看看二叉搜索树的单层递归逻辑有何不同。
因为二叉搜索树的节点是有序的所以可以有方向的去搜索。
如果root-val val搜索左子树如果root-val val就搜索右子树最后如果都没有搜索到就返回NULL。
代码如下
TreeNode* result NULL;
if (root-val val) result searchBST(root-left, val);
if (root-val val) result searchBST(root-right, val);
return result;很多录友写递归函数的时候 习惯直接写 searchBST(root-left, val)却忘了 递归函数还有返回值。
递归函数的返回值是什么? 是 左子树如果搜索到了val要将该节点返回。 如果不用一个变量将其接住那么返回值不就没了。
所以要 result searchBST(root-left, val)。
整体代码如下
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root NULL || root-val val) return root;TreeNode* result NULL;if (root-val val) result searchBST(root-left, val);if (root-val val) result searchBST(root-right, val);return result;}
};98.验证二叉搜索树
