求二叉树的最大叶子节点距离(递归)

题目: 输入一颗二叉树先序遍历的字符串,输出该二叉树的最大叶子节点距离


思路:先定义一个表示最大叶子节点距离的全局变量,然后按照后续遍历的方法访问每一个节点,

在遍历的过程中全局变量随时更新为目前出现的最大节点距离。当访问完根节点后,全局变量里

的值即为最大叶节点距离。



节点类型定义如下:

struct BTNode { char key; BTNode* lchild, *rchild; int maxLeftDepth; int maxRightDepth; BTNode(char val) :key(val), lchild(NULL), rchild(NULL), maxLeftDepth(0), maxRightDepth(0) {}; };


//存储最大叶子节点距离的全局变量

int maxDepth = 0;


//按照先序遍历的顺序输入一棵二叉树的所有节点,#代表空节点,创建一颗二叉树

void createTree(BTNode*& root)
{
	char val = getchar();
	if (val == '#')
	{
		root = NULL;
		return;
	}
	else
	{
		if (root == NULL)
		{
			root = new BTNode(val);
			createTree(root->lchild);
			createTree(root->rchild);
		}
	}
}


//后序遍历输出二叉树所有节点,验证上面建立的二叉树是否正确

void PostOrderTraversal(BTNode* root)
{
	if (root == NULL)
		return;
	PostOrderTraversal(root->lchild);
	PostOrderTraversal(root->rchild);
	cout << root->key << " ";
}


//查找最大叶子节点距离

void maxLeafDistance(BTNode* root)
{
	if (root == NULL)
		return ;

	//先访问左孩子节点
	if (root->lchild == NULL)
		root->maxLeftDepth = 0;
	if (root->lchild != NULL)
		maxLeafDistance(root->lchild);

	//再访问右孩子节点
	if (root->rchild == NULL)
		root->maxRightDepth = 0;
	if (root->rchild != NULL)
		maxLeafDistance(root->rchild);
	
	//最后访问根节点
	if (root->lchild)
	{
		int maxLeftDepOfRt = ((root->lchild->maxLeftDepth > root->lchild->maxRightDepth) ? root->lchild->maxLeftDepth + 1 :
			root->lchild->maxRightDepth + 1);
		root->maxLeftDepth = maxLeftDepOfRt;
	}
	if (root->rchild)
	{
		int maxRightDepOfRt = (root->rchild->maxLeftDepth > root->rchild->maxRightDepth) ? root->rchild->maxLeftDepth + 1 :
			root->rchild->maxRightDepth + 1;
		root->maxRightDepth = maxRightDepOfRt;
	}

	//访问完根节点后依据需要更新代表最大叶子节点距离的全局变量
	if (root->maxLeftDepth + root->maxRightDepth >maxDepth)
	{
		maxDepth = root->maxLeftDepth + root->maxRightDepth;
	}
	return ;
}


//按后序遍历的方式依次删除二叉树的每一个节点

void destroyTree(BTNode*& root)
{
	if (root != NULL)
	{
		if (root->lchild == NULL && root->rchild == NULL)
		{
			cout << "删除" << root->key << "节点" << endl;
			delete root;
			root = NULL;
			return;
		}
		destroyTree(root->lchild);
		destroyTree(root->rchild);
		cout << "删除" << root->key << "节点" << endl;
		delete root;
		root = NULL;
	}
	else
		return;
}

//main函数

int main() { BTNode* root = NULL; cout << "请按先序遍历顺序输入一颗二叉树,#代表空节点: "; createTree(root); cout << "建立的二叉树的后序遍历顺序为: "; PostOrderTraversal(root); cout << endl; maxLeafDistance(root); cout << "构造的二叉树中最大叶子节点距离为: " << maxDepth << endl; destroyTree(root); return 0; }

整理一下全部的代码:

#include<iostream> using namespace std; struct BTNode { char key; BTNode* lchild, *rchild; int maxLeftDepth; int maxRightDepth; BTNode(char val) :key(val), lchild(NULL), rchild(NULL), maxLeftDepth(0), maxRightDepth(0) {}; }; int maxDepth = 0;//代表最大叶子节点距离的全局变量 void createTree(BTNode*& root) { char val = getchar(); if (val == '#') { root = NULL; return; } else { if (root == NULL) { root = new BTNode(val); createTree(root->lchild); createTree(root->rchild); } } } void PostorderTraversal(BTNode* root) { if (root == NULL) return; PostorderTraversal(root->lchild); PostorderTraversal(root->rchild); cout << root->key << " "; } void maxLeafDistance(BTNode* root) { if (root == NULL) return ; //先访问左孩子节点 if (root->lchild == NULL) root->maxLeftDepth = 0; if (root->lchild != NULL) maxLeafDistance(root->lchild); //再访问右孩子节点 if (root->rchild == NULL) root->maxRightDepth = 0; if (root->rchild != NULL) maxLeafDistance(root->rchild); //最后访问根节点 if (root->lchild) { int maxLeftDepOfRt = ((root->lchild->maxLeftDepth > root->lchild->maxRightDepth) ? root->lchild->maxLeftDepth + 1 : root->lchild->maxRightDepth + 1); root->maxLeftDepth = maxLeftDepOfRt; } if (root->rchild) { int maxRightDepOfRt = (root->rchild->maxLeftDepth > root->rchild->maxRightDepth) ? root->rchild->maxLeftDepth + 1 : root->rchild->maxRightDepth + 1; root->maxRightDepth = maxRightDepOfRt; } //访问完根节点后依据需要更新代表最大叶子节点距离的全局变量 if (root->maxLeftDepth + root->maxRightDepth >maxDepth) { maxDepth = root->maxLeftDepth + root->maxRightDepth; } return ; } void destroyTree(BTNode*& root) { if (root != NULL) { if (root->lchild == NULL && root->rchild == NULL) { cout << "删除" << root->key << "节点" << endl; delete root; root = NULL; return; } destroyTree(root->lchild); destroyTree(root->rchild); cout << "删除" << root->key << "节点" << endl; delete root; root = NULL; } else return; } int main() { BTNode* root = NULL; cout << "请按先序遍历顺序输入一颗二叉树,#代表空节点: "; createTree(root); cout << "建立的二叉树的后序遍历顺序为: "; PostorderTraversal(root); cout << endl; maxLeafDistance(root); cout << "构造的二叉树中最大叶子节点距离为: " << maxDepth << endl; destroyTree(root); return 0; }

测试用例1:

FGHA###M##JK#B##L##

构建的二叉树如下图所示:

《求二叉树的最大叶子节点距离(递归)》

知红色路径上的两个叶子节点为最大距离叶子节点,距离为6。


运行结果如下图所示:

《求二叉树的最大叶子节点距离(递归)》

从上图可以看到运行结果正确,说明程序编码无误。




测试用例2:A#BCEG####DF#H###

构建的二叉树如下图所示:

《求二叉树的最大叶子节点距离(递归)》

知红色路径上的两个叶子节点为最大距离叶子节点,距离为6。


运行结果如下图所示:

《求二叉树的最大叶子节点距离(递归)》


从上图可以看到运行结果正确,说明程序编码无误。


    原文作者:yfainaer
    原文地址: https://blog.csdn.net/yfainaer/article/details/59486551
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞