算法训练营Day15

2023-12-15 07:23:10

#Java #递归

开源学习资料

Feeling and experience:

今日主要练习递归,深入理解递归:

二叉树的最小深度:力扣题目链接

昨天对此题也做了练习与解答,用到的是层序遍历的解法。

今天用递归来解答:

/**
 * 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 int minDepth(TreeNode root) {
    //利用递归
    //递归的终止条件?
    //1.当前节点为空
    if(root == null){
        return 0;
    }

    //2.当前节点的孩子都为空
    if(root.left==null && root.right==null){
        return 1;
    }
    int minLeft = minDepth(root.left);
    int minRight = minDepth(root.right);
    //3.当前节点的一个孩子为空
    if(root.left == null || root.right==null){
        return minLeft+minRight+1;
    }
    //递的返回值,下一级返回递给上一级的是什么?
    return Math.min(minLeft,minRight)+1;
    //加1是把当前自己算上
    }
}

对每一步都进行剖析:

首先考虑递归的时候,不要纠结递归过程中,它是如何一步一步走的,不然这样很容易绕晕。

主要清楚:

递归的终止条件:也就是“归”的含义,出口

递归的返回值:当前方法的返回值,传递给上一个方法继续执行(栈的结构)

比如这道经典的二叉树最小深度问题:

找到递归的出口条件(一共有三个):

当前节点为空时,返回0;

当前节点的孩子都为空时,返回1(把自身返回回去);

当前节点的一个孩子为空时,说明要么是左孩子为空,要么是右孩子为空,反正minLeft与minRight中有一个为0,则返回?minLeft+minRight+1;

方法的返回值:

调用的方法最后返回的是当前节点最小的深度,+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 {
    public int countNodes(TreeNode root) {
    //递归的终止条件
    if(root == null){
        return 0;
    }
    int left = countNodes(root.left);
    int right = countNodes(root.right);

    return left+right+1;
    }
}

多刷手感就来了。

理解通透了递归三部曲,运用这些简单的递归就很轻松了。

今天最主要的就是深入理解递归,能快速写出简单题的递归解法。

时光清浅处

一步一安然~

?Fighting!

文章来源:https://blog.csdn.net/momolinshaomo/article/details/134989167
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。