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

654.最大二叉树

题目链接：. - 力扣（LeetCode）

文字讲解：代码随想录

视频讲解：又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」网站：programmercarl.com， 这里刷题顺序，详细题解，应有尽有！, 视频播放量 33179、弹幕量 292、点赞数 694、投硬币枚数 512、收藏人数 88、转发人数 34, 视频作者 代码随想录, 作者简介 哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：单调队列正式登场！| LeetCode：239. 滑动窗口最大值，自底向上查找，有点难度！ | LeetCode：236. 二叉树的最近公共祖先，我更完了，你看完了吗？，坑很多！来看看你掉过几次坑 | LeetCode：106.从中序与后序遍历序列构造二叉树，一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树，回溯算法解决子集问题，如何去重？| LeetCode：90.子集II，怎么找二叉树的左下角？ 递归中又带回溯了，怎么办？| LeetCode：513.找二叉树左下角的值，调整二叉树的结构最难！| LeetCode：450.删除二叉搜索树中的节点，二叉树的高度和深度有啥区别？究竟用什么遍历顺序？很多录友搞不懂 | LeetCode：104.二叉树的最大深度，构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树https://www.bilibili.com/video/BV1MG411G7ox

思路：与根据后序和中序排序构建二叉树的做法差不多。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return createMaxTree(nums, 0, nums.length - 1);
    }

    public TreeNode createMaxTree(int[] nums, int left, int right) {
        if (left == right) {
            TreeNode root = new TreeNode(nums[left]);
            return root;
        }
        if (left > right) {
            return null;
        }
        int max = Integer.MIN_VALUE;
        int position = -1;
        for (int i = left; i <= right; i++) {
            if (nums[i] > max) {
                position = i;
                max = nums[i];
            }
        }
        TreeNode root = new TreeNode(nums[position]);

        root.left = createMaxTree(nums, left, position - 1);
        root.right = createMaxTree(nums, position + 1, right);
        return root;

    }
}

617.合并二叉树

题目链接：. - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com， 这里刷题顺序，详细题解，应有尽有！, 视频播放量 27364、弹幕量 304、点赞数 716、投硬币枚数 525、收藏人数 100、转发人数 20, 视频作者 代码随想录, 作者简介 哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索，又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树，原来这么简单？ | LeetCode：701.二叉搜索树中的插入操作，构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树，普大喜奔！二叉树章节已全部更完啦！| LeetCode：538.把二叉搜索树转换为累加树，单调队列正式登场！| LeetCode：239. 滑动窗口最大值，调整二叉树的结构最难！| LeetCode：450.删除二叉搜索树中的节点，你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树，回溯算法解决子集问题，如何去重？| LeetCode：90.子集II，梦开始的地方，Leetcode：1.两数之和，学透哈希表，map使用有技巧！https://www.bilibili.com/video/BV1m14y1Y7JK

思路：后序合并，先合并两颗树的左子树，再合并右子树，最后处理根节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        root1.val += root2.val;
        return root1;
    }
}

700.二叉搜索树中的搜索

题目链接：. - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com， 这里刷题顺序，详细题解，应有尽有！, 视频播放量 27291、弹幕量 285、点赞数 594、投硬币枚数 427、收藏人数 83、转发人数 24, 视频作者 代码随想录, 作者简介 哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树，不仅双指针，还有代码技巧可以惊艳到你！ | LeetCode：501.二叉搜索树中的众数，二叉搜索树找祖先就有点不一样了！| 235. 二叉搜索树的最近公共祖先，梦破碎的地方！| LeetCode：15.三数之和，坑很多！来看看你掉过几次坑 | LeetCode：106.从中序与后序遍历序列构造二叉树，动态规划开更了！| LeetCode：746. 使用最小花费爬楼梯，自底向上查找，有点难度！ | LeetCode：236. 二叉树的最近公共祖先，回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II，和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III，回溯算法解决子集问题，树上节点都是目标集和！ | LeetCode：78.子集https://www.bilibili.com/video/BV1wG411g7sF

思路：如果节点的值比target小，就找它左子树，反之，找它右子树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        TreeNode node = null;
        if (root.val > val) {
            node = searchBST(root.left, val);
        }
        if (root.val < val) {
            node = searchBST(root.right, val);
        }
        return node;
    }
}

98.验证二叉搜索树

题目链接：. - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com， 这里刷题顺序，详细题解，应有尽有！, 视频播放量 39606、弹幕量 565、点赞数 1026、投硬币枚数 867、收藏人数 193、转发人数 50, 视频作者 代码随想录, 作者简介 哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：【CS61B汉化】七海讲数据结构-二叉搜索树【七海Nana7mi】，二叉搜索树【图解】，数据结构-二叉树-判断给定二叉树是否为二叉排序树（BST），验证二叉搜索树，2022年计算机408数据结构代码题判断二叉搜索树问题，【LeetCode 每日一题】98. 验证二叉搜索树 | 手写图解版思路 + 代码讲解，数据结构合集 - 二叉搜索树(二叉排序树)(二叉查找树)，我更完了，你看完了吗？，手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找，最优二叉搜索树 动态规划算法https://www.bilibili.com/video/BV18P411n7Q4

思路：因为二叉搜索树树的性质，其中序遍历是升序的。方法一：可中序遍历二叉树，将遍历的值保存到集合中，如果是升序的就是二叉搜索树否则就不是二叉搜索树。方法二：定义一个指针指向上一个节点，也是通过中序遍历比较上一个节点的值，如果符合是升序的那么就是二叉搜索树，否则不是二叉搜索树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode pre = null;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean leftTreeIsBST = isValidBST(root.left);
        if (!leftTreeIsBST) {
            return false;
        }
        if (pre != null && pre.val >= root.val) {
            return false;
        }
        pre = root;
        boolean rightTreeIsBST = isValidBST(root.right);

        return rightTreeIsBST;
}
}