代码随想录算法训练营第20天

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return invert(nums, 0, nums.length);
    }
    // 1.返回值：当前子树的根节点。参数：子数组首尾（前闭后开）
    public TreeNode invert(int[] nums, int start, int end) {
        // 2.结束条件
        if(start == end) return null;
        // 3.递归逻辑
        // 3.1.找最大（及其索引号），new节点
        int max = findMax(nums, start, end);
        TreeNode root = new TreeNode(nums[max]);
        // 3.2.左右递归
        root.left = invert(nums, start, max);
        root.right = invert(nums, max + 1, end);
        // 3.3.返回节点
        return root;
    }
    public int findMax(int[] nums, int start, int end) {
        int max = start;
        for(int i = start; i < end; i++) {
            if(nums[i] > nums[max]) max = i;
        }
        return max;
    }
}

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        return invert(root1, root2);
    }
    // 1.返回值：合并当前节点下面的子树的结果
    public TreeNode invert(TreeNode root1, TreeNode root2) {
        // 2.结束条件：至少有一方为null，则返回不为null的一方，否则直接返回null
        if(root1 == null) return root2;
        if(root2 == null) return root1;
        // 3.递归逻辑：都不为null
        // 3.1.new，加和节点数值
        TreeNode root = new TreeNode(root1.val + root2.val);
        // 3.2.再递归左右
        root.left = invert(root1.left, root2.left);
        root.right = invert(root1.right, root2.right);
        // 3.3.返回节点
        return root;
    }
}

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        // node表示当前查看的节点
        TreeNode node = root;
        // 循环：若当前node为null，则说明没有找到，结束循环
        while(node != null) {
            // 找到，循环break
            if(node.val == val) break;
            // 当前值小于待寻找值，找右边
            if(node.val < val) {
                node = node.right;
                continue;
            }
            // 当前值大于待寻找值，找左边
            if(node.val > val) {
                node = node.left;
                continue;
            }
        }
        // 找到返回该节点为根的子树，否则返回null
        return node;
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> inorder = new ArrayList<>();
        traversal(root, inorder);
        // 中序一定是递增的
        if(inorder.size() == 0) return true;
        for(int i = 1; i < inorder.size(); i++) {
            System.out.println(inorder.get(i) + ' ' + inorder.get(i - 1));
            if (inorder.get(i) <= inorder.get(i - 1)) return false;
        }
        return true;
    }
    public void traversal(TreeNode cur, List<Integer> inorder) {
        if(cur == null) return;
        traversal(cur.left, inorder);
        inorder.add(cur.val);
        traversal(cur.right, inorder);
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        return invert(root, null, -1);
    }
    public boolean invert(TreeNode root, Integer parent, int direction) {
        // 2.结束条件：
        if(root == null) return true;
        // 3.递归逻辑
        if((root.left != null && root.left.val >= root.val) 
        || (root.right != null && root.right.val <= root.val)) return false;
        else return invert(root.left, root.val, 1) && invert(root.right, root.val, 2);
    }
}

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