有了昨天的钻研,今天的算法代码写的更熟了

654.最大二叉树

 Map<Integer, Integer> map = new HashMap<>();

    /**
     * <a href= "https://leetcode.cn/problems/maximum-binary-tree/">654. 最大二叉树</>
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        return constructMaximumBinaryTree(0, nums.length, nums);
    }

    public TreeNode constructMaximumBinaryTree(int start, int end, int[] nums) {
        if (start >= end) {
            return null;
        }
        int midIndex = start;
        int mid = nums[midIndex];
        for (int i = start; i < end; i++) {
            if (nums[i] > mid) {
                mid = nums[i];
                midIndex = i;
            }
        }
        TreeNode root = new TreeNode(mid);
        root.left = constructMaximumBinaryTree(start, midIndex, nums);
        root.right = constructMaximumBinaryTree(midIndex + 1, end, nums);
        return root;
    }

617.合并二叉树

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return null;
        }
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        TreeNode root = new TreeNode(root1.val + root2.val);
        TreeNode left = mergeTrees(root1.left, root2.left);
        TreeNode right = mergeTrees(root1.right, root2.right);
        root.left = left;
        root.right = right;
        return root;
    }
==============================================
在没看视频情况下写的算法
public TreeNode mergeTrees2(TreeNode root1, TreeNode root2) {
        if (isEmpty(root1) && isEmpty(root2)) {
            return null;
        }
        TreeNode root = new TreeNode(), left, right;
        if (!isEmpty(root1) && !isEmpty(root2)) {
            root.val = root1.val + root2.val;
            left = mergeTrees(root1.left, root2.left);
            right = mergeTrees(root1.right, root2.right);
        } else if (isEmpty(root1)) {
            root.val = root2.val;
            left = mergeTrees(root1, root2.left);
            right = mergeTrees(root1, root2.right);
        } else {
            root.val = root1.val;
            left = mergeTrees(root1.left, root2);
            right = mergeTrees(root1.right, root2);
        }

        root.left = left;
        root.right = right;
        return root;
    }

700.二叉搜索树中的搜索

public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        if (root.val > val) {
            return searchBST(root.left, val);
        }
        return searchBST(root.right, val);
    }

    public TreeNode searchBST2(TreeNode root, int val) {
        while (root != null) {
            if (root.val == val) {
                break;
            }
            root = root.val > val ? root.left : root.right;
        }
        return root;
    }

98.验证二叉搜索树

List<Integer> list =new ArrayList<>();

    /**
     * <A href= "https://leetcode.cn/problems/validate-binary-search-tree/">98. 验证二叉搜索树</A>
     */
    public boolean isValidBST(TreeNode root) {
        travel(root);
        for (int i = 0; i < list.size()-1; i++) {
            if(list.get(i+1)<list.get(i)){
                return false;
            }
        }
        return true;
    }
    public void travel(TreeNode cur){
        if(cur == null){
            return;
        }
        travel(cur.left);
        list.add(cur.val);
        travel(cur.right);
    }