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

654.最大二叉树

又是构造二叉树，昨天大家刚刚做完 中序后序确定二叉树，今天做这个 应该会容易一些， 先看视频，好好体会一下 为什么构造二叉树都是 前序遍历
题目链接/文章讲解：https://programmercarl.com/0654.最大二叉树.html
视频讲解：https://www.bilibili.com/video/BV1MG411G7ox

比106.从中序与后序遍历序列构造二叉树 简单点
自己做出来了
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function(nums) {
    if (nums.length === 0) return null;
    let max = Math.max(...nums);
    let index = nums.indexOf(max);
    let maxNode = new TreeNode(max);
    maxNode.left = constructMaximumBinaryTree(nums.slice(0,index));
    maxNode.right = constructMaximumBinaryTree(nums.slice(index+1));
    return maxNode;
};

617.合并二叉树

这次是一起操作两个二叉树了， 估计大家也没一起操作过两个二叉树，也不知道该如何一起操作，可以看视频先理解一下。 优先掌握递归。
题目链接/文章讲解：https://programmercarl.com/0617.合并二叉树.html
视频讲解：https://www.bilibili.com/video/BV1m14y1Y7JK

自己做出来了
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function(root1, root2) {
    if (root1 === null && root2 === null) return root1;
    if (root1 === null) return root2;
    if (root2 === null) return root1;
    let num1 = root1.val;
    let num2 = root2.val;
    let total = num1 + num2;
    let totalNode = new TreeNode(total);
    totalNode.left = mergeTrees(root1.left, root2.left);
    totalNode.right = mergeTrees(root1.right, root2.right);
    return totalNode;
};

700.二叉搜索树中的搜索

递归和迭代 都可以掌握以下，因为本题比较简单， 了解一下 二叉搜索树的特性
题目链接/文章讲解: https://programmercarl.com/0700.二叉搜索树中的搜索.html
视频讲解：https://www.bilibili.com/video/BV1wG411g7sF

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    if (root === null) return null;
    if (root.val > val) {
        return searchBST(root.left, val);
    } else if (root.val <val) {
        return searchBST(root.right, val);
    } else {
        return root;
    }
};

98.验证二叉搜索树

遇到 搜索树，一定想着中序遍历，这样才能利用上特性。
但本题是有陷阱的，可以自己先做一做，然后在看题解，看看自己是不是掉陷阱里了。这样理解的更深刻。
题目链接/文章讲解：https://programmercarl.com/0098.验证二叉搜索树.html
视频讲解：https://www.bilibili.com/video/BV18P411n7Q4

这题有一点坑
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    let maxValue =Number.MIN_SAFE_INTEGER;
    const inOrder = (node) => {
        if (node === null) return true;
    
        let left = inOrder(node.left);
        if (!left || maxValue >= node.val) {
            return false;
        }
        maxValue = node.val;
        let right = inOrder(node.right);
        return left && right;
    }
    return inOrder(root);
};