二叉树路径相关算法题|带权路径长度WPL|最长路径长度|直径长度|到叶节点路径|深度|到某节点的路径非递归(C)

带权路径长度WPL

二叉树的带权路径长度(WPL)是二叉树所有叶节点的带权路径长度之和，给定一棵二叉树T，采用二叉链表存储，节点结构为

其中叶节点的weight域保存该节点的非负权值，设root为指向T的根节点的指针，设计求WPL的算法

算法思想

方法1，树中全部叶节点的带权路径长度之和
采用递归思想
二叉树的WPL值 = 树中全部叶节点的带权路径长度之和 = 根节点左子树中全部叶节点的带权路径长度之和 + 根节点右子树中全部叶节点的带权路径长度之和
叶节点的带权路径长度 = 该节点的weight域的值 x 该节点的深度
设根节点的深度为0，若某节点的深度为d，其子节点的深度为d+1
递归过程中，如果遍历到叶节点，返回该节点的带权路径长度，否则返回其左右子树的带权路径长度之和

先遍历5，d是0，不是叶子节点，递归3和7，d为1，3不是叶子节点，7是叶子节点，返回1x7，再递归1和4，d为2，都是叶子节点，返回1x2和4x2，所以WPL为2+8+7=17

typedef struct node
{
	int weight;
	struct node *left, *right;
}BTNode;

// 传入根节点，调用递归函数，初始深度d为0
int WPL(BTNode* root)
{
	return WPL1(root, 0);
}

// 传入节点和该节点的深度
int WPL1(BTNode* root, int d)
{
	// 如果该节点是叶子节点，返回该叶子节点的weightxd，也就是带权路径长度
	if (root->left == NULL && root->right == NULL)
		return (root->weight * d);
	// 否则递归该节点的左孩子和右孩子，子节点的深度为根节点的深度+1
	else
		return (WPL1(root->left, d + 1) + WPL1(root->right, d + 1));
}

WPL1是一个递归函数，用来计算从当前节点开始的WPL

最长路径长度

给定一个二叉树的root，返回最长的路径的长度，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。两个节点之间的路径的长度由它们之间的边数表示

算法思想

符合要求的左子树路径最大长度leftpath，符合要求的右子树路径最大长度rightpath，最后的路径长度为当前路径，与rightpath+leftpath最大值，注意全局变量的初始化位置

第一层
递归计算root的左右孩子的最长单向路径
右节点存在且与当前节点值相等，都是5
rightpath = right+1

第二层
right是右节点的DFS返回的值；
递归计算这个节点的左右孩子的最长单向路径，
同样右节点存在且与当前值相等，都是5
rightpath = right+1

第三层
right是右孩子返回的值，
递归左右孩子，为空，返回0
left和right都是0，path也是0，最后返回0
返回第二层
right是0，rightpath是1，path更新为1，返回1
返回第一层
right是1，rightpath是2，path更新为2，返回2

int path;   // 全局变量，用于存储当前发现的最长路径长度
// 返回两个正数中的较大值
int Max(int a, int b)
{
	return a >= b ? a : b;
}
// 递归地计算以root为根的子树中，以相同节点值构成的最长路径
int DFS(BTNode* root)
{
	// 如果当前节点为空，返回0，因为没有路径
	if (root == NULL)
		return 0;

	int left;
	int right;
	int leftpath = 0;
	int rightpath = 0;
	// 递归计算左子树和右子树的最长单向路径
	// left是左子树的最长路径，right是右子树的最长路径
	left = DFS(root->left);
	right = DFS(root->right);
	// 如果左节点存在且与当前节点值相等，最长路径+1
	if ((root->left) && (root->left->val == root->val))
		leftpath = left + 1;
	// 如果右节点存在且与当前节点值相等，最长路径+1
	if ((root->right) && (root->right->val == root->val))
		rightpath = right + 1;
	// leftpath+rightpath，当前节点处的最长路径的长度，经过当前节点
	// 更新path
	path = Max(path, leftpath + rightpath);
	// 返回从当前节点向下延伸的最长单项路径，用于供上层节点继续计算
	return Max(leftpath, rightpath);
}
int longestUnivaluePath(BTNode* root)
{
	if (root == NULL)
		return 0;
	path = 0;
	DFS(root);
	return path;
}

直径长度

给定一个二叉树，计算它的直径长度。一棵二叉树的直径长度是任意两个节点路径长度中的最大值。这条路径可能穿过也可能不穿过根节点

算法思想

递归求得节点的左子树的最大深度和右子树的最大深度，相加便是经过该节点的直径，遍历每个节点，更新最大值便可得到该二叉树的最大直径。

1. 写出一个求树的最大深度的函数
2. 递归调用这个函数，求得每个节点的左子树最大深度和右子树最大深度，相加

第一层
将rootA传入depth求深度，传入sum记录直径
递归计算左右子树B和C的深度
第二层
B继续递归左右子树的深度，D和F
C为叶子节点，没有左右孩子，left和right为0，new也就是直径为1，sum更新为1，返回深度为1
第三层
D为叶子节点，new为1，sum还是1，返回深度为1
F为叶子节点，new为1，sum还是1，返回深度为1
返回第二层
B，的left和right都是1，B的new也就是直径是3，sum更新为3，返回深度为2
返回第一层
A，left为2，right为1，new也就是直径为4，sum更新为4，返回深度为3
最后sum=4，返回sum-1 = 3

// 返回两个整数中的较大值
int max(int a, int b)
{
	return a > b ? a : b;
}

// 递归计算二叉树的深度，同时更新全局变量记录直径
int depth(BTNode* root, int* sum)
{
	// 如果当前节点为空，返回深度为0
	if (root == NULL)
		return 0;
	// 左子树的最大深度
	int left = depth(root->left, sum);
	// 右子树的最大深度
	int right = depth(root->right, sum);
	// 经过根节点的直径，左子树最大深度与右子树最大深度之和
	int new = left + right + 1;
	// 更新sum，记录到目前为止的最大直径
	*sum = max(*sum, new);
	// 返回该节点深度的最大值，等于左右子树的最大深度+1
	return max(left, right) + 1;
}

int dimeterBT(BTNode* root)
{
	if (root == NULL)
		return 0;
	int sum = 0;
	depth(root, &sum);
	// 返回sum-1，将节点数转换为边数作为直径的定义
	return sum - 1;
}

到叶节点路径

给你一个二叉树的根节点root，按任意顺序，返回所有从根节点到叶子节点的路径

算法思想

深度优先遍历二叉树，要考虑当前节点以及它的孩子节点，如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点
如果当前节点是叶子节点，则在当前路径末尾添加该节点后就得到了从根节点到叶子节点的路径

将根节点的值1，入到stack深度下标的位置上，深度为0

有左右孩子，先递归左孩子，深度+1=1
2，入栈

有右孩子，递归右孩子，5入栈，depth为2

这时候左右孩子节点都为空
将1->2->5的路径保存

• 动态分配一个字符串缓冲区tmp。用于存储当前路径的字符串
  1001是缓冲区的长度
• len=0，记录路径字符串的当前长度，即字符串的写入位置，起始为0，表示字符串从头开始写入
• 遍历当前路径中的所有节点值，即stack；使用sprintf追加到路径字符串tmp中
• 添加叶节点值，在路径字符串的末尾，添加当前叶子节点的值
• 将路径字符串存储到结果数组

返回1节点，递归右孩子3，深度为1，入栈，会覆盖掉2，变成3

// 定义二叉树节点结构 
typedef struct node 
{ 
	int val; 
	struct node* left; 
	struct node* right; 
} BTNode; 

// 辅助函数：递归生成路径 
void generatePaths(BTNode* root, char** paths, int* returnSize, int* stack, int depth) 
{ 
	if (root == NULL) 
		return; 
	// 将当前节点加入路径栈 
	stack[depth] = root->val; 
	// 如果是叶子节点，生成路径字符串 
	if (root->left == NULL && root->right == NULL) 
	{ 
		// 分配路径字符串 
		char* tmp = (char*)malloc(1001); 
		int len = 0; 
		// 构建路径字符串 
		for (int i = 0; i < depth; i++) 
		{ 
			len += sprintf(tmp + len, "%d->", stack[i]); 
		} 
		// 添加叶子节点值 
		sprintf(tmp + len, "%d", root->val); 
		
		
		// 将路径存储到结果数组 
		paths[(*returnSize)++] = tmp; 
		return; 
	} 
	
	// 递归遍历左、右子树 
	generatePaths(root->left, paths, returnSize, stack, depth + 1); 
	generatePaths(root->right, paths, returnSize, stack, depth + 1); 
} 

// 主函数：生成所有路径 
char** binaryTreePaths(BTNode* root, int* returnSize) 
{ 
	// 分配结果数组 
	char** paths = (char**)malloc(sizeof(char*) * 1001); 
	*returnSize = 0; 
	// 路径栈 
	int stack[1001]; 
	// 调用递归函数 
	generatePaths(root, paths, returnSize, stack, 0); 
	
	return paths; 
}

• binaryTreePaths，输入：root，二叉树的根节点，returnSize，用来返回路径数量
• 返回paths，存储路径字符串的数组
• paths是一个指针数组，用来存储每条路径的字符串
• stack用来记录当前节点的路径值
• generatePaths用来来递归生成路径

generatePaths

• 如果节点root为NULL，直接返回，(递归退出条件)
• 将当前节点的值存入栈stack[depth]中
• depth表示当前路径的深度
  处理叶子节点
• 创建字符串，遍历路径栈stack，通过sprintf拼接路径值，将路径字符串的结果保存在paths中
• 增加路径数量returnSize
  遍历左右子树
• 如果当前节点不是叶子节点，遍历递归左子树和右子树
• 子树深度为depth+1

深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点形成树的一条路径，最长路径的长度为树的深度
9

算法思想

如果二叉树为空，深度为0，如果二叉树只有根节点，深度为1
如果二叉树的根节点只有左子树，深度为左子树的深度+1
如果二叉树的根节点只有右子树，深度为右子树的深度+1
如果二叉树的根节点既有既有左子树又有右子树，深度为左右子树深度最大者+1

int maxDepth(BTNode* root)
{
	if (root == NULL)
		return 0;

	// 当前节点的左子树的深度
	int Lenleft = maxDepth(root->left);
	// 当前节点的右子树的深度
	int Lenright = maxDepth(root->right);

	// 返回左右子树的深度的较大者+1
	return Lenleft > Lenright ？ Lenleft+1 : Lenright+1;
}

到某节点的路径非递归

假设二叉树采用链式存储结构进行存储，root为根节点，p为任意给定节点
求从根节点到p之间路径的非递归算法

算法思想

采用后序非递归遍历二叉树，栈中保留从根节点到当前节点的路径上的所有节点

• cur是当前遍历的节点
• s是栈，用来存储当前节点及其祖先节点，用于后续回溯
• tag数组用于标记每个节点的左右子树是否已经被访问
• top用来表示栈的当前高度
  while循环用于实现二叉树的深度优先遍历，只要当前节点不为空或者栈不为空就继续
  while循环表示从当前cur节点开始，一直往左遍历，直到没有左子树为止
  每次访问一个节点，将该节点入栈，并设置tag为0，表示其右子树未被访问
  如果当前节点cur就是p，就打印从根节点到p的路径，通过s栈表示

由于p是3节点，将1，2，4，入栈

处理右子树，检查tap里的数据，如果右子树被访问过，就弹出该节点，跳过所有已经完全访问过的节点
如果该节点的右子树未被访问，就会进入右子树进行遍历，

遍历4节点的右子树，tag置为1，节点为空，直接返回

这是循环过来，4被访问过，出栈

再遍历2的右节点，

// 查找从根节点到指定节点p的路径
void Path(BTNode* root, BTNode* p)
{
	if (root == NULL || p == NULL)
		return;

	BTNode* cur = root;
	// 存储节点路径的栈
	int s[MaxSize];
	// 栈的当前高度
	int top = 0;
	// 标记左右子树是否访问过
	int tag[MaxSize] = {0};

	while (cur || top > 0)
	{
		// 向左走直到最左叶子节点
		while (cur)
		{
			// 将当前节点入栈
			s[++top] = cur;
			// 标记为未访问右子树
			tag[top] = 0;
			
			// 找到目标节点p
			if (cur == p)
			{
				printf("从根节点到p节点的路径为\n");
				for (int i = 1; i <= top; i++)
				{
					printf("%d", s[i]->data);
					if (i < top)
						printf("->");
					printf("\n");
					return;
				}
			}

			// 继续遍历左子树
			cur = cur->left;
		}
		
		// 如果当前节点的左子树遍历完，回溯到父节点
		while (top > 0 && tag[top] == 1)
			// 出栈
			top--;
		
		// 访问右子树
		if (top > 0)
		{
			// 访问当前节点的右子树
			cur = s[top];
			// 进入右子树
			cur = cur->right;
			// 标记右子树已访问
			tag[top] = 1;
		}
	}
}