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

一、654.最大二叉树

力扣

1. 找终止条件：当l>r时，说明数组中已经没元素了，自然当前返回的节点为null。
2. 每一级递归返回的信息是什么：返回的应该是当前已经构造好了最大二叉树的root节点。
3. 一次递归做了什么：找当前范围为[l,r]的数组中的最大值作为root节点，然后将数组划分成[l,bond-1]和[bond+1,r]两段，并分别构造成root的左右两棵子最大二叉树。

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return maxTree(nums, 0, nums.length - 1);
    }
    public TreeNode maxTree(int[] nums, int left, int right) {
        if(left > right) {
            return null;
        }
        //bond为当前数组中最大值的索引
        int bond = findMaxValue(nums, left, right);
        TreeNode root = new TreeNode(nums[bond]);
        root.left = maxTree(nums, left, bond - 1);
        root.right = maxTree(nums, bond + 1, right);
        return root;
    }
    public int findMaxValue(int[] nums, int left, int right) {
            int max = Integer.MIN_VALUE, maxIndex = left;
            for(int i = left; i <= right; i++){
                if(max < nums[i]){
                    max = nums[i];
                    maxIndex = i;
                }
            }
            return maxIndex;
        }
}

二、合并二叉树

力扣

思路：1、找终止条件：因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了啊（如果t2也为NULL也无所谓，合并之后就是NULL）。反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。

2、每一级递归返回的信息是什么：返回的应该是当前已经合并好了二叉树的root1节点。

3、一次递归做了什么：就是将两个二叉树上的节点值相加。

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. 二叉搜索树中的搜索

力扣

思路：二叉搜索树记住等于，大于，小于三个判断条件即可。递归或者迭代都可以。注意在哪里返回，需不需要接受返回值。

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        //题目说给的节点数不会为0为什么还要加不等于空，因为后面递归传入的left，right会为空
        if(root == null || root.val == val) {
            return root;
        }
        if(root.val > val) {
            //为神马在这里就直接return，因为如果在这左边递归找到了结果需要马上结束代码，如果不return，则后面代码还会继续执行
            return searchBST(root.left, val);
        }else if(root.val < val) {
            return searchBST(root.right, val);
        }
        return null;
    }
}
 
class Solution {
    // 迭代，利用二叉搜索树特点，优化，可以不需要栈
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null)
            if (val < root.val) root = root.left;
            else if (val > root.val) root = root.right;
            else return root;
        return null;
    }
}

四、98.验证二叉搜索树

力扣

思路1:自己独立写的，用中序遍历，判断是否为一个递增的序列。

class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> path = new ArrayList<>();
        inorder(root, path);
        for(int i = 1; i < path.size(); i++) {
            if(path.get(i) <= path.get(i - 1)) {
                return false;
            }
        }
        return true;
    }
    public void inorder(TreeNode root, List<Integer> path) {
        if(root == null) return;
        inorder(root.left, path);
        path.add(root.val);
        inorder(root.right, path);
    }
}

思路2:使用了集合记录中序遍历的元素，为什么不直接在中序遍历递归的同时判断中序遍历是否是有序的呢？中序遍历，一直更新maxValue，一旦发现maxValue>= root.val，就返回false，注意元素相同时候也要返回false。 

class Solution {
    int maxValue = Integer.MIN_VALUE;
     public boolean isValidBST(TreeNode root) {
         if(root == null) return true;
         boolean left = isValidBST(root.left);
         // 中序遍历，验证遍历的元素是不是从小到大
         if (maxValue < root.val) {
             maxValue = root.val; // 中
         }else {
             return false;
         }
         boolean right = isValidBST(root.right);
         return left && right;
    }
}

什么时候递归需要返回值 ？

代码随想录