三步走解决递归问题

递归三步走

严格按照这三步, 轻松解决递归问题

1. 给函数下定义很多时候困扰我们的?

在写递归函数前, 我们先要给要写的这个递归函数下一个定义.

一旦下完了这个定义, 我们就认为函数具有了这个功能(尽管这个函数我们并未书写)

然后在书写代码的时候就帮这个被我们下过定义的函数当成具有这个功能的函数来写

注意: 不要过分的关注函数本身, 下完定义, 函数就具有这个功能, 不需要纠结如何实现

就以二叉树的前序遍历为例子, 我们给这个函数下一个定义, 就是前序遍历这棵二叉树

class TreeNode
{
	public:
    TreeNode* left;
    TreeNode* right;
    int val;
}

// 来给函数下一个定义
void bfs(TreeNode* root); 
// 该函数的功能: 前序遍历以root为根节点的这棵二叉树

2. 每一层做什么?

在下完定义以后, 就可以来分析函数该做什么了

• 对于二叉树的前序遍历这个例子, 函数要做的事情很简单, 就是将当前的root节点的val值输出

cout << root->val << endl;

• 与此同时, 还需前序遍历root的左右子节点

注意! 注意! 注意! 这里是重点

我们来回顾一下刚刚给bfs(TreeNode*)函数下的定义: // 该函数的功能: 前序遍历以root为根节点的这棵二叉树

我们下完定义, 就应该默认这个函数具有了这个功能

因此, 我们要实现前序遍历root的左右子节点, 就只需要用我们刚刚下过定义的这个函数

bfs(root->left);// 前序遍历left子树
bfs(root->right);// 前序遍历right子树

再说一遍!再说一遍!下完定义之后我们就应该把函数当成有我们下定义的这个功能, 尽管我们函数一点没写

3. 什么时候做?

最后, 我们需要判断一下, 2中所做的事情的顺序

接着以二叉树的前序遍历为例子, 2中我们已经分析完了, 要做3件事

• 将当前的root节点的val值输出 1
• 还需前序遍历root的左子节点 2
• 还需前序遍历root的右子节点 3

这棵树前序遍历的结果应该是

1 2 3 5 7 3 6 8 9

应该不难想到:

• 其中1是将当前的root节点的val值输出 即1
• 而 2 3 5 7是对左子节点的前序遍历 即2
• 3 6 8 9是对右子节点的前序遍历 即3

所以执行的顺序就是 1→2→ 3

那么这个函数的大致轮廓就出来了

void bfs(TreeNode* root); 
{
    cout << root->val << endl;
    
    bfs(root->left);// 前序遍历left子树
	bfs(root->right);// 前序遍历right子树
}

* 最后的最后 处理一下边界

边界问题一般不难分析

还是说这棵树, 应该不难看出, 当root值为nullptr的时候, 这个函数就应该推出了

if(root == nullptr)
{
    return;
}

函数代码示例

@brief 前序遍历一棵二叉树
void bfs(TreeNode* root); 
{
    if(root == nullptr)
	{
    	return;
	}
    
    cout << root->val << endl;
    
    bfs(root->left);// 前序遍历left子树
	bfs(root->right);// 前序遍历right子树
}