[数据结构与算法]代码随想录算法训练营第20天 | 654.最大二叉树，3. 无重复字符的最长子串，617. 合并二叉树，98. 验证二叉搜索树

代码随想录算法训练营第20天 | 654.最大二叉树，3. 无重复字符的最长子串，617. 合并二叉树，98. 验证二叉搜索树

654.最大二叉树

1. 构造二叉树中 整体的思路是用 前序遍历 中左右 因为要把中先构造出来 才能构造左右节点
2. 首先确定递归函数的返回值 为node 传入参数为 数组(每次数组可以进行切片)
3. 终止条件为 当数组内只剩下一个节点时 说明已经到达叶节点
4. 中 找到数组最大元素下标 创建为 中节点
5. 判断 当前数组还剩大于等于1个元素 然后向左右递归 传入参数 为分割后的数组 保持左闭右开的区间原则
6. 返回值为 root

/**
 * 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 createTree(nums);

    }

    public TreeNode createTree(int[] nums){
        //终止条件
        //题目中说数组长度不等于0 所以不用判断数组为空的情况
        if(nums.length == 1){
            return new TreeNode(nums[0]);
        }

        //中 
        int maxValue = 0;
        int nodeIndex = 0;
        for(int i =0;i<nums.length;i++){
            if(nums[i]>maxValue){
                maxValue = nums[i];
                nodeIndex = i;
            }
        }

        //创建中节点
        TreeNode node = new TreeNode(maxValue);

        //向左右递归
        //区间定义为左闭右开 需要向左或向右的空间内至少还有一个节点 才可以
        if(nodeIndex>=1){
            int[] newnums = Arrays.copyOfRange(nums,0,nodeIndex);
            node.left = createTree(newnums);

        }

        if(nums.length-nodeIndex>1){
            
            node.right = createTree(Arrays.copyOfRange(nums,nodeIndex+1,nums.length));            
        }

        return node;


    }
}

3. 无重复字符的最长子串

1. 滑动窗口去滑动遍历字符串 有左右两个指针 遇到重复的元素就将左指针移到下一位 同时每次都取最大的窗口长度
2. 判断重复元素的数据结构可以使用 HashMap
3. 注意有两种情况 1种是两个重复元素之间都是不一样的元素 那么更新左指针的时候就可以到左指针下一位
4. 但是假如两个重复元素之间都是一样的元素 那么左指针就必须更新到中间重复元素更新完的left的地方 所以要比较是left大还是
5. map.get(s.charAt(i))大

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        if(s.length()==0) return 0;

        int left = 0;
        int max = 0;

        //遍历字符串
        for(int i=0;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){
                //如果重复 就将左指针移到下一位
                left = Math.max(map.get(s.charAt(i))+1,left);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }


        return max;



    }
}

617. 合并二叉树

1. 一起操作两个二叉树并不复杂 递归函数传入两个二叉树 然后同时遍历 中左右
2. 可以直接在root1上面操作 也可以新建一个节点操作

/**
 * 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.val+=root2.val;

        //向左右递归
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);

        return root1;





    }

    

}

700. 二叉搜索树中的搜索

1. 因为是在二叉搜索树中 左子节点值小于根节点值小于右子节点值 所以无需确定前中后遍历顺序
2. 终止条件为 当节点为空 或者 找到相等值时 返回

递归

/**
 * 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 res = null;

        if(val>root.val){
            res = searchBST(root.right,val);
        }

        if(val<root.val){
            res = searchBST(root.left,val);
        }

        return res;

    }
}

迭代法

/**
 * 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) {
        //迭代法
        while(root!=null){
            if(val>root.val){
                root = root.right;
            }else if(val<root.val){
                root = root.left;
            }else{
                return root;
            }
        }
        return null;

    }
}

98. 验证二叉搜索树

1. 中序遍历时 为左中右 若将结果存入数组中去 数组是有序的 可以利用这一点来判断结果

/**
 * 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 {
    List<Integer> arr = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        traversal(root);
        for(int i=1;i<arr.size();i++){
            if(arr.get(i)<=arr.get(i-1)){
                return false;
            }
        }

        return true;
        
        
    }

    public void traversal(TreeNode node){
        //终止条件
        if(node==null) return;

        //中序遍历 左中右
        

        //左递归
        traversal(node.left);
        //中
        arr.add(node.val);
        //右
        traversal(node.right);
    }
}

用双指针比较前后2个节点值得大小

1. 注意点 定义节点时需 定义全局变量 因为每次递归都为调用

/**
 * 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 left = isValidBST(root.left);
        //中
        if(pre!=null && pre.val>=root.val){
            return false;
        }
        pre = root;
        //右
        boolean right = isValidBST(root.right);
        return left && right;
    }
}

用一个变量暂存上一节点的值

1. 注意点 定义该变量时 不能在递归函数里面定义 要定义全局变量

/**
 * 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 {
    long max = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        

        //终止条件
        if(root==null) return true;

        //中序遍历

        boolean left = isValidBST(root.left);

        if(max>=root.val){
            return false;
        }else{
            max=root.val;
        }

        boolean right = isValidBST(root.right);

        return left && right;
        
    }
}