有多少人真正会递归？

程序员小熊

发布于 2021-05-28 12:14:05

5050

发布于 2021-05-28 12:14:05

前言

对数据结构与算法有所了解的童鞋，一定对递归（recursion）并不陌生，事实上递归在计算机领域中发挥重要的作用，是很多算法和数据结构的基础，无论是排序算法（归并排序、快速排序），还是对于一些比如树的数据结构，亦或是一些图中的算法（比如深度优先遍历）等都涉及到递归。本文主要通过二叉树介绍递归。

递归

递归是指在函数的定义中使用函数自身的方法。比较典型的例子就是斐波拉契数列 f(n) = f(n - 1) + f(n - 2)，n ≥ 2。

二叉树

二叉树是天然的递归结构。其定义是：如果一个节点，它有左右两个孩子，且左右孩子都是一颗二叉树，则就存在一棵以该节点为根的二叉树。从定义中可看出定义的是二叉树，但在定义里用二叉树来定义二叉树。因此二叉树的定义本身就是递归的定义。如下图示。

04. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

/ \

9 20

/ \

15 7

返回它的最大深度 3 。

解题思路

由于二叉树具有天然的递归性，所以可以通过递归去做，

可以分别计算当前节点的左右子树的最大深度，然后取两者的最大值再加 1（当前节点的深度），就是这颗二叉树的最大深度。

需要注意的是递归终止条件：当前节点为空，深度为 0。

Show me the Code

// c语言
int maxDepth(TreeNode* root) {
    /* 递归终止条件，节点为空 */
    if (root == NULL) {
        return 0;
    }
    return fmax(maxDepth(root->left), maxDepth(root->right)) + 1;
}

// golang
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：输出：

解题思路

要翻转一颗二叉树，可以先翻转当前节点的左子树，再翻转当前节点的右子树，最后再把当前节点翻转之后的左右子树交换一下位置即可。递归终止条件：当前节点为空，直接返回空。如下图示：

Show me the Code

// c++
TreeNode* invertTree(TreeNode* root) {
    if(root == NULL) {
        return NULL;
    }

    /* 翻转根节点的的左/右子树 */
    invertTree(root->left); 
    invertTree(root->right); 
    /* 交换翻转之后的左右子树 */
    swap(root->left, root->right);
    return root;
}

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。

叶子节点是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

解题思路

要判断一颗树中是否存在根节点到叶子节点所有节点值相加等于给定目标值的路径，只需要分别从根节点到其左/右子树中查找是否存在该路径即可，可以递归地在左右子树中查找。

Show me the Code

// java
boolean hasPathSum(TreeNode root, int targetSum) {
    /* 递归终止条件，当前节点为叶子节点 */
    if (root == null) {
        return targetSum == 0;
    }

    /* 当前节点左子树寻找 */
    if (hasPathSum(root.left, targetSum - root.val)) {
        return true;
    } 

    /* 当前节点右子树寻找 */
    if (hasPathSum(root.right, targetSum - root.val)) {
        return true;
    }
    return false;
}

运行结果

结果分析

上面代码中，递归的终止条件是 node == null，这是不对的，因为忽视了其上一层的父节点是否是一个叶子节点。

修改后的 Code

boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }

    /* 递归终止条件，当前节点为叶子节点 */
    if (root.left == null && root.right == null) {
        return targetSum == root.val;
    } 

    return hasPathSum(root.left, targetSum - root.val) || 
            hasPathSum(root.right, targetSum - root.val);
}

运行结果