代码随想录day17--二叉树的应用5

LeetCode654.最大二叉树

题目描述：

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 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(vector<int>& 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){//处理最大值左侧的元素vector<int> newVec(nums.begin(),nums.begin()+maxValueIndex);node->left = constructMaximumBinaryTree(newVec);}if(maxValueIndex < nums.size()-1){//处理最大值右侧的元素vector<int> newVec(nums.begin()+maxValueIndex+1,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;queue<TreeNode*> 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;}
};

总结：因为二叉树搜索树的有序性，遍历的时候要比普通二叉树还要简单一些，但是一定要记住二叉搜索的特性，因为我们之后的题目中还需要使用。

LeetCode98.验证二叉搜索树

题目描述：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

解题思路：

·给定一个结点进行判断是否是二叉搜索树，也就是给定的二叉树需要满足有效二叉树的定义，也就是说给的这个二叉树进行中序遍历后，可以得到一个从小到大递增的数组（无相同元素）

·也可以使用递归法进行求解，对二叉树进行遍历，若满足条件则为平衡二叉树，若不满足则不为

使用数组的代码如下：

class Solution {
public:vector<int> vec;void traversal(TreeNode* root){//使用中序遍历if(root == NULL) return ;traversal(root->left);vec.push_back(root->val);traversal(root->right);}bool isValidBST(TreeNode* root) {traversal(root);for(int i = 1;i < vec.size();i++){if(vec[i] <= vec[i-1]) return false;//一定是小于等于因为搜索二叉树中元素不相等}return true;}
};

使用递归法代码如下：

class Solution {
public:long long maxValue = LONG_MIN;bool isValidBST(TreeNode* root) {if(root == NULL) return true;bool left = isValidBST(root->left);if(maxValue < root->val){maxValue = root->val;}else return false;bool right = isValidBST(root->right);return right&&left;}
};

易错点：

·在递归法中，不能简单的比较左节点小于中间节点，右节点大于中间节点。否则会造成，右子树的左节点小于根节点的情况。我们要比较的左子树的所有节点小于中间节点，右子树所有节点大于中间节点。

总结：可能会有想不到的情况，但是都是正常的，如果要准确无误的使用递归，需要大量的练习。