代码随想录算法训练营第十九天 | 654.最大二叉树，617.合并二叉树，700.二叉搜索树中的搜索，98.验证二叉搜索树

标签：right TreeNode val int 二叉 搜索 二叉树 root left

一、参考资料

最大二叉树

题目链接/文章讲解：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

合并二叉树

题目链接/文章讲解：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

二叉搜索树中的搜索

题目链接/文章讲解: https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html

视频讲解：https://www.bilibili.com/video/BV1wG411g7sF

验证二叉搜索树

题目链接/文章讲解：https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV18P411n7Q4

二、LeetCode654.最大二叉树

https://leetcode.cn/problems/maximum-binary-tree/description/

示例一：

示例二：

给定一个不重复的整数数组 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]
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    TreeNode* constructMaxTree(vector<int>& nums, int leftBegin, int rightEnd) {
        int maxVal = nums[leftBegin];
        int index = leftBegin;
        if (leftBegin >= rightEnd) return nullptr;
        // if (nums.size() == 1) return new TreeNode(nums[0]);
        for (int i = leftBegin; i < rightEnd; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                index = i;
            }
        }
        cout << maxVal << " " << index << endl;
        TreeNode* root = new TreeNode(maxVal);
        // 左
        if (index > 0) {
            root->left = constructMaxTree(nums, leftBegin, index);
        }
        // 右
        if (index < rightEnd- 1) {
            root->right = constructMaxTree(nums, index + 1, rightEnd);
        }
        return root;
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.size() == 1) {
            return new TreeNode(nums[0]);
        }
        return constructMaxTree(nums, 0, nums.size());   // 左闭右开
    }
};

注意事项记录：

class Solution {
// 几点需要注意的：
// 1. 所有区间边界问题，左闭右开
// 2. 递归结束的条件：递归结束的条件是区间左端点的值≥区间右端点的值
// 3. 在采用这种传下标的方法时，maxVal和index的初始化要用下标来表示，而不是默认0
// 4. 加if判断是为了不让空节点进入递归
private:
    TreeNode* constructMaxTree(vector<int>& nums, int leftBegin, int rightEnd) {
        int maxVal = nums[leftBegin];
        int index = leftBegin;
        if (leftBegin >= rightEnd) return NULL;
        for (int i = leftBegin; i < rightEnd; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                index = i;
            }
        }
        // cout << maxVal << " " << index << endl;
        TreeNode* root = new TreeNode(maxVal);
        // 左   // 这里加了判断是为了不让空节点进入递归
        if (index > 0) {
            root->left = constructMaxTree(nums, leftBegin, index);
        }
        // 右   // 这里加了判断是为了不让空节点进入递归
        if (index < rightEnd- 1) {
            root->right = constructMaxTree(nums, index + 1, rightEnd);
        }
        return root;
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.size() == 1) {
            return new TreeNode(nums[0]);
        }
        return constructMaxTree(nums, 0, nums.size());   // 左闭右开
    }
};

三、LeetCode617.合并二叉树

https://leetcode.cn/problems/merge-two-binary-trees/description/

示例1：

给你两棵二叉树： 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]
提示：
两棵树中的节点数目在范围 [0, 2000] 内
-10^4 <= Node.val <= 10^4

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
// 本题旨在考察如何同步处理两个树 —— 采用前中后序遍历均可以！（代码以前序为例）
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (root1 == NULL) return root2;  // 如果root1为空，合并之后就应该是root2
        if (root2 == NULL) return root1;  // 如果root2为空，合并之后就应该是root1
        // 修改了root1的数值和结构
        root1->val += root2->val;                                // 中
        root1->left = mergeTrees(root1->left, root2->left);      // 左
        root1->right = mergeTrees(root1->right, root2->right);   // 右
 
        return root1;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
// 不改变root1，而是新建一棵树
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (root1 == NULL) return root2;  // 如果root1为空，合并之后就应该是root2
        if (root2 == NULL) return root1;  // 如果root2为空，合并之后就应该是root1
        // 新建树
        TreeNode* root = new TreeNode(root1->val + root2->val); // 中
        root->left = mergeTrees(root1->left, root2->left);      // 左
        root->right = mergeTrees(root1->right, root2->right);   // 右
 
        return root;
    }
};

队列迭代法：（不是很熟练——参考代码随想录）

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        queue<TreeNode*> que;
        que.push(t1);
        que.push(t2);
        while(!que.empty()) {
            TreeNode* node1 = que.front(); que.pop();
            TreeNode* node2 = que.front(); que.pop();
            // 此时两个节点一定不为空，val相加
            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);
            }
 
            // 当t1的左节点 为空 t2左节点不为空，就赋值过去
            if (node1->left == NULL && node2->left != NULL) {
                node1->left = node2->left;
            }
            // 当t1的右节点 为空 t2右节点不为空，就赋值过去
            if (node1->right == NULL && node2->right != NULL) {
                node1->right = node2->right;
            }
        }
        return t1;
    }
};

四、LeetCode700.二叉搜索树中的搜索

https://leetcode.cn/problems/search-in-a-binary-search-tree/description/

示例1：

示例2：

给定二叉搜索树（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 输出：[]
提示：
数中节点数在 [1, 5000] 范围内
1 <= Node.val <= 10^7
root 是二叉搜索树
1 <= val <= 10^7

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
// version1: 递归法
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        TreeNode* res = NULL;
        if (root == NULL || root->val == val) return root;
        if (val < root->val) res = searchBST(root->left, val);
        if (val > root->val) res = searchBST(root->right, val);
 
        return res;
    }
};
 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
// version2: 继续递归（简化版）
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;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
// version3: 迭代法
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;
    }
};

因为二叉搜索树的有序性，遍历的时候要比普通二叉树简单很多。

五、LeetCode98.验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/description/

回顾一下中序遍历的迭代法写法

// https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html#%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86-%E8%BF%AD%E4%BB%A3%E6%B3%95

示例1：

示例2：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：
输入：root = [2,1,3] 输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
树中节点数目范围在[1, 104] 内
-2^31 <= Node.val <= 2^31 - 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
// version1：直接比较（为了满足了测试样例而定义初始值）
public:
    long long maxVal = LONG_MIN;   // 注意：这个最小值应该写到递归函数外面，不然每次递归子树时都会重新进入
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);   // 左
        if (root->val > maxVal) {
            maxVal = root->val;               // 中
        } else {
            return false;
        }
        bool right = isValidBST(root->right);  //右
        return left && right;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
// version2：双指针优化 —— 需要注意的是 判断前一个节点≥当前节点时，返回false，而不是仅大于
public:
    TreeNode* pre = NULL;   // pre记录前一个节点的值
    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;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
// version 3: 迭代法模拟二叉树中序遍历
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* pre = NULL;   // 记录前一个节点
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->left;   // 左
            } else {
                cur = st.top();    // 中
                st.pop();
                if (pre != NULL && pre->val >= cur->val) {
                    return false;
                } else {
                    pre = cur;
                }
                cur = cur->right;   // 右
            }
        }
        return true;
    }
};

我写的版本

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
// version 4: 我写的迭代法模拟二叉树中序遍历
// https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html#%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86-%E8%BF%AD%E4%BB%A3%E6%B3%95
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* pre = NULL;   // 记录前一个节点
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->left;
            }
            if (cur != NULL) {
                st.push(cur);
                cur = cur->left;   // 左
            } else {
                cur = st.top();    // 中
                st.pop();
                if (pre != NULL && pre->val >= cur->val) {
                    return false;
                } else {
                    pre = cur;
                }
                cur = cur->right;   // 右
            }
        }
        return true;
    }
};

• 陷阱1

不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。

• 陷阱2

样例中最小节点 可能是int的最小值，如果这样使用最小的int来比较也是不行的。

此时可以初始化比较元素为longlong的最小值。

进一步解决陷阱2，引入了version2的代码，通过双指针优化

总结：

做到现在已经能够看完视频独立写出代码了，下一步通过复习希望能熟练掌握解题的思路，还有什么类型的题用前序遍历，什么类型的题用后序遍历，什么类型的题用中序遍历，什么类型的题不用考虑遍历顺序等等。

参考以下这个博主的解答：

https://blog.csdn.net/weixin_44561338/article/details/107946716

• 前序遍历（中左右）

• 第一次访问就输出数据

• 适合静态访问

• 中序遍历（左中右）

• 对于二分搜索树，输出结果是有序的

• 适合顺序输出结果

• 后序遍历（左右中）

• 对节点操作时必访问过其子节点

• 适合进行破坏性操作（删除节点）

刷题加油鸭~~

标签：right,TreeNode,val,int,二叉,搜索,二叉树,root,left
From： https://www.cnblogs.com/ucaszym/p/17093512.html