算法训练营Day18

#Java #二叉树 #递归

开源学习资料

Feeling and experiences：

?

最大二叉树：力扣题目链接

给定一个不重复的整数数组?nums 。?最大二叉树?可以用下面的算法从?nums 递归地构建:?

该题掌握了递归就非常简单了，思路：

找到数组中，最大元素的下标，以该元素为分界，左边的是它的左子树部分，右边的是它的右子树部分，再利用递归遍历其左子树与右子树即可。

/**
 * 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 dfs(nums,0,nums.length-1);
    }
    public TreeNode dfs(int [] nums,int left,int right){
        //终止条件
        if(left>right){
            return null;
        }
        //获得数组中最大元素的下标！
        int best = left;
        for(int i= left+1;i<=right;i++){
            if(nums[i] > nums[best]){
                best = i;
            }
        }
        //递归左右子树！
        TreeNode node = new TreeNode(nums[best]);
        node.left = dfs(nums,left,best-1);
        node.right = dfs(nums,best+1,right);
        return node;
    }
}

代码很好理解，dfs方法中，传入的参数为数组nums，起始值left，末尾值right

递归结束条件：当left > right

for循环获得最大元素的下标，图示如下：

清楚每层做什么事情，怎么递归到下一层。

合并二叉树：力扣题目链接

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

这道题，最开始我还在思考如何把这两颗树合并。

后面想到了，遍历二叉树时用到的递归，当遍历到的节点为空时，本来应该返回null，但如果是两课树合并的话，就可以把另一颗树遍历到的子树返回为该树。

理清楚思路后，代码就非常好写了：

/**
 * 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) {
    //用递归遍历一棵树时，终止条件是当前节点为空，返回null
    //这里只需要把null改成 把另一颗树返回来就行
    //因为这里是覆盖嘛
    if(root1 == null){
        return root2;
    }
    if(root2 == null){
        return root1;
    }
    //重叠的值，叠加
    TreeNode sum = new TreeNode(root1.val+root2.val);
    //递归左子树
    sum.left = mergeTrees(root1.left , root2.left);
    //递归右子树
    sum.right = mergeTrees(root1.right , root2.right);

    return sum;
    }
}

改一下终止条件的返回值即可。

二叉搜索树中的搜索：力扣题目链接

给定二叉搜索树（BST）的根节点?root?和一个整数值?val。

你需要在 BST 中找到节点值等于?val?的节点。 返回以该节点为根的子树。 如果节点不存在，则返回?null?。

首先要知道二叉搜索树的性质：

每个节点的左子树的值都比该节点小；

每个节点的右子树的值都比该节点大；

/**
 * 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){
        return null;
    }
    //找到了该值，则返回该节点
    if(root.val == val){
        return root;
    }
    //小于则去左子树找
    if(val < root.val){
    return searchBST(root.left,val);
    }
    //大于则去右子树找
    if(val > root.val){
        return searchBST(root.right,val);
    }
    
    return root;
    }
}

?用三目运算简化了左右递归的代码：

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (val == root.val) {
            return root;
        }
        return searchBST(val < root.val ? root.left : root.right, val);
    }
}

验证二叉搜索树：力扣题目链接

这道题还是只要清楚了二叉搜索树的结构特点就很简单了。

/**
 * 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 boolean isValidBST(TreeNode root) {
    return dfs(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    public boolean dfs(TreeNode node,long lower,long upper){
        //如果当前节点为空，则返回真
        if(node == null){
            return true;
        }
        if(node.val <= lower || node.val >= upper){
            return false;
        }
        //对于左子树，上界变为当前节点的值
        //对于右子树，下界变为当前节点的值
        return dfs(node.left,lower,node.val) && dfs(node.right,node.val,upper);


    }
}

主要的就是用到了 最大值? 和? 最小值? Long类型

使用?`Long.MIN_VALUE`?和?`Long.MAX_VALUE`?作为初始的下界（lower）和上界（upper）是为了确保在初始调用时，所有可能的?`int`?值都在这个范围内。在?Java?中，`int`?类型的范围是从?`-2^31`?到?`2^31-1`，而?`long`?类型的范围是从?`-2^63`?到?`2^63-1`，所以?`Long.MIN_VALUE`?和?`Long.MAX_VALUE`?能够涵盖所有?`int`?类型的值。

对于每个节点，我们需要确保其值在某个特定范围内。这个范围是由它的所有祖先节点定义的。对于左子节点，其值必须小于其父节点的值，并且大于或等于其所有祖先节点中左侧的最小值（这就是为什么我们用?`Long.MIN_VALUE`?作为初始的下界）。

类似地，对于右子节点，其值必须大于其父节点的值，并且小于或等于其所有祖先节点中右侧的最大值（这就是为什么我们用?`Long.MAX_VALUE`?作为初始的上界）。

在递归调用时，这些上界和下界会随着每一层的遍历而更新，以确保每个节点都符合二叉搜索树的性质。例如，当递归检查左子树时，会将当前节点的值作为新的上界传递给左子树的递归调用，因为左子树中的所有节点都应该小于这个上界（即当前节点的值）。同样，当检查右子树时，当前节点的值会成为新的下界。

只恐夜深花睡去，

放下高烛照红妆~

Fighting！

?

?

?