算法训练营Day15

#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!