day 20 二叉树 part05

654.最大二叉树

又是构造二叉树，昨天大家刚刚做完中序后序确定二叉树，今天做这个应该会容易一些，先看视频，好好体会一下为什么构造二叉树都是前序遍历

题目链接/文章讲解：https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV1MG411G7ox

617.合并二叉树

这次是一起操作两个二叉树了，估计大家也没一起操作过两个二叉树，也不知道该如何一起操作，可以看视频先理解一下。优先掌握递归。

题目链接/文章讲解：https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV1m14y1Y7JK

700.二叉搜索树中的搜索

递归和迭代都掌握

二叉搜索树的特点是根节点比左孩子节点要大，比右孩子节点要小。

代码随想录

递归法:注意遍历左右子树的时候要返回函数，如果左右子树都遍历不到的时候，就返回空

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root == NULL || root->val == val) return root;if (root->val > val) return searchBST(root->left, val);if (root->val < val) return searchBST(root->right, val);return NULL;}
};

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while (root != NULL) {if (root->val > val) root = root->left;else if (root->val < val) root = root->right;else return root;}return NULL;}
};

98.验证二叉搜索树

遇到搜索树，一定想着中序遍历，这样才能利用上特性。

注意根节点要比所有左子树的所有节点都要小，要比所有右子树的节点都要大。

方法一：maxValue来记录前一个节点的数值，如果前一个节点的数值（按照中序的遍历顺序，数组的值应该是递增的（如果是平衡二叉树的话），否则就不是平衡二叉树）
方法二：用pre记录前一个节点，当前节点和pre进行比较，pre进行更新。

class Solution {
public:TreeNode* pre = NULL; // 用来记录前一个节点bool isValidBST(TreeNode* root) {if (root == NULL) return true;bool left = isValidBST(root->left);if (pre != NULL && pre->val >= root->val) return false;pre = root; // 记录前一个节点bool right = isValidBST(root->right);return left && right;}
};

也可以用迭代法，只用增加一个指针指向前一个节点和判断什么时候返回fasle以及更新前一个指针的。
注意：while中是两个条件是或的情况！！！！

代码随想录

class Solution {
public:bool isValidBST(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;TreeNode* pre = NULL; // 记录前一个节点while (cur != NULL || !st.empty()) {if (cur != NULL) {st.push(cur);cur = cur->left;                // 左} else {cur = st.top();                 // 中st.pop();if (pre != NULL && cur->val <= pre->val)return false;pre = cur; //保存前一个访问的结点cur = cur->right;               // 右}}return true;}
};