二叉树的递归详解:以例题计算二叉树第k层为例

1.代码速览

1.1节点的构建

#include<iostream>
using namespace std;
class ListNode
{
public:
	friend void fun();
	friend int TreeKLevel(ListNode* root, int k);
	ListNode(int val)
		:_val(val)
		,leftnext(nullptr)
		,rightnext(nullptr)
	{}
private:
	int _val = 0;
	class ListNode* leftnext;
	class ListNode* rightnext;
};

1.2二叉树的创建

void fun()
{
	ListNode* n1 = new ListNode(1);
	ListNode* n2 = new ListNode(2);
	ListNode* n3 = new ListNode(3);
	ListNode* n4 = new ListNode(4);
	ListNode* n5 = new ListNode(5);

	n1->leftnext = n2;
	n2->leftnext = n3;
	n2->rightnext = n5;
	n1->rightnext = n4;

	// 假设我们要计算第3层的节点数  
	int level2Nodes = TreeKLevel(n1, 3);
	cout << level2Nodes << endl;
	delete n1;
	delete n2;
	delete n3;
	delete n4;
	delete n5;
}

1.3计算第K层节点的个数

int TreeKLevel(ListNode* root, int k)
{
	if (root == nullptr)
		return 0;
	if (k == 1)
		return 1;
	int leftk = TreeKLevel(root->leftnext, k - 1);
	int rightk = TreeKLevel(root->rightnext, k - 1);
	return leftk + rightk;
}

2.代码详解

2.1函数栈帧的创建

数的栈帧（Stack Frame）是程序运行时在调用栈（Call Stack）上分配的一个内存块，用于存储函数执行时的局部变量、参数、返回地址等信息。当函数被调用时，一个新的栈帧会被创建并压入调用栈的顶部；当函数执行完毕并返回时，其对应的栈帧会被销毁并从调用栈中弹出。即函数每次被调用的时候,都会创建一个栈帧.

2.2函数栈帧的弹出

在一个函数执行完其return语句之后,这个函数栈帧便会被弹出,执行的下一个语句便会回到函数上一次被调用的地方.

2.3函数递归调用图示

2.4叙述此段代码运行逻辑

这段代码开始运行,其参数列表接收由程序员传递过来的树的根部root以及目标层数k

在运行的过程中,先碰到    int leftk = TreeKLevel(root->leftnext, k - 1);        后,会进行一下函数的调用,根据函数的栈帧的相关知识,函数在调用的同时候会开辟新的栈帧,并接着在当前开辟的栈帧中运行,与此同时,k也会减去1,在此代码    int leftk = TreeKLevel(root->leftnext, k - 1);不断进行调用开辟栈帧的同时,k最终也会减到"1",此时将会执行代码

遇到return 1;遇到return语句后,会弹出当前的栈帧并且回到上一次调用的地方

int leftk = TreeKLevel(root->leftnext, k - 1);并且将刚才的return 1中的1返回并且赋值给int leftk并使用left进行保存,之后便是    int rightk = TreeKLevel(root->rightnext, k - 1);的调用,在每次调用这个函数并且开辟栈帧对每一个节点的left子树进行遍历的时候,return的值会被返回给int rightk然后在每一个父节点的栈帧中,使用return lefk+rightk对它的左右子树进行节点个数的相加,然后依靠return再返回给上一个栈帧的leftk或者rightk,用这个思路最后可以得出第k层的节点个数

2.5使用画图的方法进行更形象的说明