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

前言
状态：654AC、617AC 可优化、700AC、98 不会
更新

1	24.06.07 初始记录

初步题解

654 最大二叉树

题目链接：(https://leetcode.cn/problems/maximum-binary-tree/)

public static TreeNode constructMaximumBinaryTree(int[] nums) {  
    if (nums.length == 0) {  
        return null;  
    }  
  
    int maxIndex = getMaxIndex(nums);  
    TreeNode root = new TreeNode(nums[maxIndex]);  
    if (nums.length == 1) {  
        return root;  
    }  
  
    root.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, maxIndex));  
    root.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, maxIndex + 1, nums.length));  
    return root;  
}  
  
private static int getMaxIndex(int[] nums) {  
    int max = Integer.MIN_VALUE;  
    int maxIndex = -1;  
    for (int i = 0; i < nums.length; i++) {  
        if (nums[i] > max) {  
            maxIndex = i;  
            max = nums[i];  
        }  
    }  
    return maxIndex;  
}

617 合并二叉树

题目链接：(https://leetcode.cn/problems/merge-two-binary-trees/)

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {  
    if (root1 == null && root2 == null) {  
        return null;  
    }  
  
    int value1 = root1 == null ? 0 : root1.val;  
    int value2 = root2 == null ? 0 : root2.val;  
  
    TreeNode node = new TreeNode(value1 + value2);  
  
    if (root1 == null) {  
        node.left = mergeTrees(null, root2.left);  
        node.right = mergeTrees(null, root2.right);  
    } else if (root2 == null){  
        node.left = mergeTrees(root1.left, null);  
        node.right = mergeTrees(root1.right, null);  
    } else {  
        node.left = mergeTrees(root1.left, root2.left);  
        node.right = mergeTrees(root1.right, root2.right);  
    }  
    return node;  
}

700 二叉搜索树中的搜索

题目链接：(https://leetcode.cn/problems/search-in-a-binary-search-tree)

/**  
 * BFS 
 */
public TreeNode searchBST(TreeNode root, int val) {  
    if (root == null) {  
        return null;  
    }  
    if (val == root.val) {  
        return root;  
    } else if (val < root.val) {  
        return searchBST(root.left, val);  
    } else {  
        return searchBST(root.right, val);  
    }  
}  
  
/**  
 * DFS 
 */
 public TreeNode searchBSTDFS(TreeNode root, int val) {  
    while (root != null) {  
        if (val == root.val) {  
            return root;  
        } else if (val < root.val){  
            root = root.left;  
        } else {  
            root = root.right;  
        }  
    }  
    return null;  
}

98 验证二叉搜索树

题目链接：(https://leetcode.cn/problems/validate-binary-search-tree/)

只比较了左节点小于中间节点，右节点大于中间节点，实际上要加上左子树所有节点小于中间节点，右子树所有节点大于中间节点

// 没有通过，少算了一种情况
public boolean isValidBST(TreeNode root) {  
    if (root == null) {  
        return true;  
    }  
  
    // 左子树不为空并且大于  
    if (root.left != null && root.left.val >= root.val) {  
        return false;  
        // 右子树不为空并且小于  
    } else if (root.right != null && root.right.val <= root.val) {  
        return false;  
    }  
  
    return isValidBST(root.left) && isValidBST(root.right);  
}

看解析

654 最大二叉树

题目链接/文章讲解：(https://programmercarl.com/0654.最大二叉树.html)

视频讲解：https://www.bilibili.com/video/BV1MG411G7ox

617 合并二叉树

题目链接/文章讲解：(https://programmercarl.com/0617.合并二叉树.html)

视频讲解：https://www.bilibili.com/video/BV1m14y1Y7JK

// 优化后
public TreeNode mergeTrees1(TreeNode root1, TreeNode root2) {  
    if (root1 == null && root2 != null) {  
        return root2;  
    } else if (root1 != null && root2 == null) {  
        return root1;  
    } else if (root1 == null && root2 == null) {  
        return null;  
    } else {  
        TreeNode node = new TreeNode(root1.val + root2.val);  
        node.left = mergeTrees(root1.left, root2.left);  
        node.right = mergeTrees(root1.right, root2.right);  
        return node;  
    }  
}

700 二叉搜索树中的搜索

题目链接/文章讲解：(https://programmercarl.com/0700.二叉搜索树中的搜索.html)

视频讲解：https://www.bilibili.com/video/BV1wG411g7sF

二叉搜索树是一个有序树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树

98 验证二叉搜索树

题目链接/文章讲解：(https://programmercarl.com/0098.验证二叉搜索树.html)

视频讲解：https://www.bilibili.com/video/BV18P411n7Q4

关键在于：中序遍历下，输出的二叉搜索树节点的数值是有序序列。

public boolean isValidBST(TreeNode root) {  
    List<Integer> list = new ArrayList<>();  
    inorder(root, list);  
  
    if (list.size() <= 1) {  
        return true;  
    }  
    for (int i = 0; i < list.size() - 1; i++) {  
        if (list.get(i) >= list.get(i + 1)) {  
            return false;  
        }  
    }  
    return true;  
}  
  
private void inorder(TreeNode root, List<Integer> list) {  
    if (root == null) {  
        return;  
    }  
    inorder(root.left, list);  
    list.add(root.val);  
    inorder(root.right, list);  
}  
  
/**  
 * 单次循环搞定
 * 双指针法
 */  
TreeNode max;  
public boolean isValidBST1(TreeNode root) {  
    if (root == null) {  
        return true;  
    }  
    // 左  
    boolean left = isValidBST1(root.left);  
    if (!left) {  
        return false;  
    }  
    // 中  
    if (max != null && root.val <= max.val) {  
        return false;  
    }  
    max = root;  
    // 右  
    return isValidBST1(root.right);  
}