day 17|
654.最大二叉树
654.最大二叉树 | 代码随想录
笔记：
构造二叉树的时候一般都使用前序遍历（中左右），因为一般都需要先把节点创建好后再去递归遍历他的左右子树。
实操出现问题：
为什么要判断不为空？因为前面的截止条件里面没有空的情况。那空节点怎么构造？实际上在创建这个new_node的时候就已经构造好了，如果maxindex左/右没有值了，就不会进入判断，从而保持原来的值为nullptr
代码/比较
class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {//截止条件：如果只有一个数字了，则返回当前构造的nodeif(nums.size()==1)return new TreeNode(nums[0]);//单层递归逻辑：中左右遍历顺序；中：寻找最大值，构造节点；左右：依次递归构造左右子树，注意传入的数组应该是不同的。最后返回当前构造的节点；//中，寻找最大值int maxval=0;int maxindex=0;for(int i=0;i<nums.size();i++){if(maxval<nums[i]){maxindex=i;maxval=nums[i];}}TreeNode* new_node=new TreeNode(maxval);//左//为什么要判断不为空？因为前面的截止条件里面没有空的情况。那空节点怎么构造？实际上在创建这个new_node的时候就已经构造好了，如果maxindex左/右没有值了，就不会进入判断，从而保持原来的值为nullptrif(maxindex>0){vector<int> nums_left(nums.begin(),nums.begin()+maxindex);new_node->left=constructMaximumBinaryTree(nums_left);}//右if(maxindex<nums.size()-1){ vector<int> nums_right(nums.begin()+maxindex+1,nums.end());new_node->right=constructMaximumBinaryTree(nums_right);}return new_node;}
};
617.合并二叉树
617.合并二叉树 | 代码随想录
笔记：
自己的想法与代码问题：
1.输入参数：两个根节点。输出参数：得到的二叉树根节点。
2.截止条件：如果两个节点都是null，返回null
3.单层递归的逻辑：首先构造中节点为两个值相加（如果有一个为空，则加0即可）；依次向左右递归生成左右子树即可
代码如下：
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//遍历顺序：前序遍历（中左右）//截止条件：如果两个节点都是null，返回nullif(root1==nullptr&&root2==nullptr)return nullptr;//单词递归逻辑：首先构造中节点为两个值相加（如果有一个为空，则加0即可）；依次向左右递归生成左右子树即可TreeNode* new_node;if(root1==nullptr&&root2!=nullptr)new_node=new TreeNode(root2->val);else if(root2==nullptr&&root1!=nullptr)new_node=new TreeNode(root1->val);elsenew_node=new TreeNode(root1->val+root2->val);new_node->left = mergeTrees(root1 ? root1->left : nullptr, // 如果root1为空，传递nullptrroot2 ? root2->left : nullptr // 如果root2为空，传递nullptr);new_node->right = mergeTrees(root1 ? root1->right : nullptr, // 如果root1为空，传递nullptrroot2 ? root2->right : nullptr // 如果root2为空，传递nullptr);return new_node;}
};
出现的问题：在向下一层递归的时候要注意，如果是root1/root2是空指针，应该向下继续传递空指针，否则会操作空指针导致程序崩溃。
课程中的笔记：
1.输入参数：两个根节点。输出参数：得到的二叉树根节点。
2.截止条件：如果其中一个节点为null，返回另一个树的当前遍历节点
3.单层递归的逻辑：构建一个二叉树结点，其中的值以当前两个值得和赋值，然后依次遍历左右子树。
代码如下：
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//遍历顺序：前序遍历（中左右）//截止条件：如果其中一个节点为null，返回另一个树的当前遍历节点if(root1==nullptr) return root2;if(root2==nullptr) return root1;//单层递归逻辑：构建一个二叉树结点，以两个结点得值的和赋值，再依次遍历左右子树TreeNode* new_node=new TreeNode(root1->val+root2->val);new_node->left=mergeTrees(root1->left,root2->left);new_node->right=mergeTrees(root1->right,root2->right);return new_node;}
};
思考：如果返回的是root1/root2，就代表着这个root1/root2结点同时存在于两个树之中。
700.二叉搜索树中的搜索
700.二叉搜索树中的搜索 | 代码随想录
递归：
二叉搜索树的定义：
- 非空左子树的所有键值小于其根结点的键值。
- 非空右子树的所有键值大于其根结点的键值。
- 左、右子树都是二叉搜索树。
1.截止条件：如果搜索到了，则直接返回，如果当前是null，也直接返回。
2.单层递归逻辑：如果当前的值比val小，当前的值应该大一点才对，所以向右递归；如果当前值比val大了，向左递归
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {//截止条件：如果搜索到了，则直接返回，如果当前是null，也直接返回。if(root==nullptr) return nullptr;if(root->val==val) return root;//单层递归逻辑：如果当前的值比val小，当前的值应该大一点才对，所以向右递归；如果当前值比val大了，向左递归TreeNode* result=nullptr;if(root->val<val) result=searchBST(root->right,val);if(root->val>val) result=searchBST(root->left,val);return result;}
};
迭代：
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {//迭代法while(root){if(root->val>val) root=root->left;else if(root->val<val)root=root->right;else if(root->val==val)return root;}return nullptr;}
};注意中间不能多次操作指针，否则会出现操作空指针的情况。
98.验证二叉搜索树
笔记：
中序遍历下，二叉搜索树是一个有序序列
注意二叉搜索树的定义：
- 非空左子树的所有键值小于其根结点的键值。
- 非空右子树的所有键值大于其根结点的键值。
- 左、右子树都是二叉搜索树。
要注意是左子树和右子树的所有值。
1.截止条件：如果是空，返回true
2.递归逻辑：使用中序遍历（左中右）。遍历左子树；如果前面一个节点的值大于等于现在节点了，则返回false;遍历右子树;如果左右子树都是二叉搜索树，则返回true
代码：
class Solution {
public:TreeNode* prenode=nullptr;//记录前面一个值bool isValidBST(TreeNode* root) {//截止条件：如果是空，返回trueif(root==nullptr) return true;//递归逻辑：使用中序遍历（左中右）。遍历左子树；如果前面一个节点的值大于等于现在节点了，则返回false;遍历右子树;如果左右子树都是二叉搜索树，则返回truebool left_isvalid=isValidBST(root->left);if(prenode!=nullptr&&prenode->val>=root->val)return false;elseprenode=root;bool right_isvali=isValidBST(root->right);return left_isvalid&&right_isvali;}
};
1