做视频网站视频用什么插件吗,iphone开发网站,昌平网站开发公司,wordpress yilia主题LeetCode654.最大二叉树
题目描述#xff1a;
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点#xff0c;其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后…LeetCode654.最大二叉树
题目描述
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。 示例 1 输入nums [3,2,1,6,0,5]
输出[6,3,5,null,2,0,null,null,1]
解释递归调用如下所示
- [3,2,1,6,0,5] 中的最大值是 6 左边部分是 [3,2,1] 右边部分是 [0,5] 。- [3,2,1] 中的最大值是 3 左边部分是 [] 右边部分是 [2,1] 。- 空数组无子节点。- [2,1] 中的最大值是 2 左边部分是 [] 右边部分是 [1] 。- 空数组无子节点。- 只有一个元素所以子节点是一个值为 1 的节点。- [0,5] 中的最大值是 5 左边部分是 [0] 右边部分是 [] 。- 只有一个元素所以子节点是一个值为 0 的节点。- 空数组无子节点。示例 2 输入nums [3,2,1]
输出[3,null,2,null,1]
解题思路
·对于构建二叉树这类题目都是使用的先序遍历进行构建因为先序遍历是先对根结点进行操作再对左右子树进行递归
·找到数组中的最大元素后再用递归法将最大数的左右元素进行递归即可解题
代码如下
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(maxValue nums[i]){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()maxValueIndex1,nums.end());node-right constructMaximumBinaryTree(newVec);}return node;}
};
难点
有些同学会对递归中的if条件的使用比较困惑一般而言如果让空节点空指针进入递归久不加if如果不让空节点进入递归就需要使用if进行限制同样的终止条件也会相应的调整。
总结本题解题代码虽稍有繁琐但是递归的逻辑比较清晰所以适合基础较为薄弱的同学进行观看学习。
LeetCode617.合并二叉树
题目描述
给你两棵二叉树 root1 和 root2 。
想象一下当你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠而另一些不会。你需要将这两棵树合并成一棵新二叉树。合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。 示例 1 输入root1 [1,3,2,5], root2 [2,1,3,null,4,null,7]
输出[3,4,5,5,4,null,7]示例 2
输入root1 [1], root2 [1,2]
输出[2,2]
解题思路 ·本题可以根据是使用中左右进行相加或层次相加进行求解也就是递归法与迭代法
·本题使用先序遍历较为简单因为根据题目可知是先对根节点计算再做之后的操作
·很多同学会困惑如果其中一个结点为null如何运算但是如果将null也看作一个值再进行相加那么就简单很多了
递归法代码如下
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 NULL) return root2;//若root1的结点为空则赋值为root2的值if(root2 NULL) return root1;//若root2的结点为空则赋值为root1的值root1-val root2-val;//中root1-left mergeTrees(root1-left,root2-left);//左root1-right mergeTrees(root1-right,root2-right);//右return root1;}
};
迭代法代码如下
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 NULL) return root2;//与递归法同理if(root2 NULL) return root1;queueTreeNode* que;que.push(root1);que.push(root2);while(!que.empty()){TreeNode* node1 que.front();que.pop();TreeNode* node2 que.front();que.pop();node1-val node2-val;//根结点相加if(node1-left ! NULL node2-left ! NULL){//两树的左子树都不为空加入队列中que.push(node1-left);que.push(node2-left);}if(node1-right ! NULL node2-right ! NULL){//两数的右子树都不为空加入队列中que.push(node1-right);que.push(node2-right);}if(node1-left NULL node2-left ! NULL){// root1的左子树为空root2的左子树不为空node1-left node2-left;//将root2中左子树的值赋值给root1中}if(node1-right NULL node2-right ! NULL){//root1的右子树为空root2的右子树不为空node1-right node2-right;//将root2中右子树的值赋值给root1}}return root1;}
};
易错点
·有同学在使用迭代法的时候可能会有疑问为什么只讨论当t1的左结点或右结点为空时的情况而不讨论t1的左结点或右结点不为空的情况呢首先我们提前说明了null也算值赋值给t1并没有什么意义。因为我们是返回的root1只需对root1的值有变动即可。
总结我们总是习惯于只操作于一个二叉树遇到要操作两个二叉树就有些发懵了但是只要我们分开处理找到需要递归或者迭代的切入点其实和只操作一个二叉树的思想是一样的。
LeetCode700.二叉搜索树
题目描述
给定二叉搜索树BST的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在则返回 null 。 示例 1: 输入root [4,2,7,1,3], val 2
输出[2,1,3]示例 2: 输入root [4,2,7,1,3], val 5
输出[]
解题思路
·需要明白二叉搜索树的定义和性质并且本题不需要考虑遍历顺序因为二叉搜索树自带顺序
同样的本题也有递归法与迭代法两种方法进行求解
递归法
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;}
};
迭代法
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while(root ! NULL){if(root-val val) return searchBST(root-left,val);else if(root-val val) return searchBST(root-right,val);else return root;}return NULL;}
};
总结因为二叉树搜索树的有序性遍历的时候要比普通二叉树还要简单一些但是一定要记住二叉搜索的特性因为我们之后的题目中还需要使用。
