代码随想录算法训练营，9月13日 | 654.最大二叉树，617.合并二叉树，700.二叉搜索树中的搜索，98.验证二叉搜索树

654.最大二叉树
题目链接：654.最大二叉树
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰最大二叉树
日期：2024-09-13

想法：根据昨天中后序列构造二叉树的经验，要找到数组中的最大值的位置，可以设置两个指针表示子树的范围（左闭右开）
Java代码如下：

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTree1(nums, 0, nums.length);
    }
    public TreeNode constructMaximumBinaryTree1(int[] nums, int left, int right){
        if(right == left) return null;
        if(right - left == 1) return new TreeNode(nums[left]);
        int maxIndex = left;
        int maxVal = nums[maxIndex];
        for(int i = left + 1; i < right; i++){
            if(nums[i] > maxVal){
                maxIndex = i;
                maxVal = nums[i];
            }
        }
        TreeNode root = new TreeNode(maxVal);
        root.left = constructMaximumBinaryTree1(nums, left, maxIndex);
        root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, right);
        return root;
    }
}

617.合并二叉树
题目链接：617.合并二叉树
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰合并二叉树
日期：2024-09-13

想法：两个二叉树一起遍历，如何节点值相加。
Java代码如下：

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2;
        if(root2 == null) return root1;
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }
}

总结：精髓在，确定终止条件，树1节点为空，返回树2节点，树2节点为空返回树1节点，这样都空的话也能返回null。

700.二叉搜索树中的搜索
题目链接：700.二叉搜索树中的搜索
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰二叉搜索树中的搜索
日期：2024-09-13

想法：首先要知道二叉搜索树的性质，左边总比右边小，当前遍历值比目标值大就往左，反之往右。
Java代码如下：

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val){
            return root;
        }
        if(val < root.val) {
            return searchBST(root.left, val);
        }
        else{
            return searchBST(root.right, val);
        }
    }
}

总结：注意终止条件包含了找到和找完没找到。

98.验证二叉搜索树
题目链接：98.验证二叉搜索树
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰验证二叉搜索树
日期：2024-09-13

想法：首先要明确遍历顺序为中序，如果满足二叉搜索树，则按中序出来是递增的，用一个节点来记录前一个遍历的值，比较大小。
Java代码如下：

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