leetcode 解题启发 -- 递归

谁践踏了优雅 2023-05-31 02:52 27阅读 0赞

**递归的定义：直接或间接的调用自身称为递归**

递归的特点：本质是分而自治的思想，顾名思义，递和归。递是传递、归是回归，所以递归满足一下的两点：

*  递、继续调用
 *  归、收敛条件

递归的思路：

*  将原问题分解为规模较小的问题进行处理（ 分解后的问题与原问题完全相同，但规模较小）
 *  设置收敛条件（递归未到达边界时，继续递归，到达边界条件时，递归结束）

这里通过一个简单的例子直观感受下，leetcode617.合并二叉树

题目描述：

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:
    
    输入: 
    	Tree 1                     Tree 2                  
              1                         2                             
             / \                       / \                            
            3   2                     1   3                        
           /                           \   \                      
          5                             4   7                  
    
    输出: 
    合并后的树:
    	     3
    	    / \
    	   4   5
    	  / \   \ 
    	 5   4   7

根据分而治之的思想，我们可以这样去思考：

*  根节点1和根节点2合并处理
 *  把左节点看成新的根节点，根节点1和根节点2合并处理
 *  … 直至二叉树的最后一层
 *  把右节点看成新的根节点，根节点1和根节点2合并处理
 *  … 直至二叉树的最后一层

上述的思路步骤，也就是大问题可以由多个小问题分开解决，这就为递归解决提供了可能，代码如下：

public class Solution {
        public TreeNode merge(TreeNode t1, TreeNode t2) {
            //收敛条件： 某个二叉树到达最后一层
            if (t1 == null || t2 == null) {
                return t1 != null ? t1 : t2;
            }
            //根节点相加
            t1.val += t2.val;
            //根据左右子树分开递归调用
            t1.left = merge(t1.left, t2.left);
            t1.right = merge(t1.right, t2.right);
            return t1;
        }
    }

相应的题型，以下leetcode题目的求解思路跟上边的一样：

*  101.对称二叉树
 *  104.二叉树的最大深度
 *  105.从前序遍历和中序遍历序列构造二叉树
 *  114.二叉树展开为链表

当然leetcode一些题目中所用的递归思路是更复杂的，像字符串操作、斐波那契数列、链表操作等等都有应用，但是递归的本质是相同的，是在简单递归的外层，加了诸多条件限制。