二叉树深度的中间值（后序遍历）

最新推荐文章于 2022-03-07 20:20:01 发布

Alaso_soso

最新推荐文章于 2022-03-07 20:20:01 发布

阅读量703

点赞数 2

分类专栏：力扣刷题文章标签： c++ 深度优先

本文链接： https://blog.csdn.net/qq_44808827/article/details/119911382

版权

力扣刷题专栏收录该内容

33 篇文章 0 订阅

订阅专栏

这篇博客介绍了如何求解给定二叉树的叶子节点深度的中间值，即最小深度和最大深度的平均值。首先分别讲解了如何计算二叉树的最大深度和最小深度，通过深度优先搜索实现。对于最大深度，递归遍历左右子树并取较大值加一。对于最小深度，考虑左右子树为空或不为空的情况，返回合适的最小深度。最后，将两者相加除以二得到中间值。

摘要由CSDN通过智能技术生成

题目描述：

给定一个二叉树，找出其叶子节点深度的中间值。

叶子节点的深度是从根节点到叶子节点的路径上的节点数量。

最小深度是从根节点到最近叶子节点的路径上的节点数量。

最大深度是从根节点到最远叶子节点的路径上的节点数量。

中间值为叶子节点最小深度和最大深度的平均值。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

3

/ \

9 20

/ \

15 7

它的最小深度为2，最大深度为3，则中间值为(2+3)/2=2.5

算法思路：

此题的实现思路可以结合力扣上两道简单的树的题目。分别为：

二叉树的最小深度
二叉树的最大深度

二叉树的最大深度：

算法思路：

特殊情况处理：如果root为空，返回0；

求二叉树的最大深度：就是深度优先搜索树的左子树和右子树，然后取两者的最大值，再加一，加一的原因在于，需要加上当前节点，我理解的为加上需要递归的结点。

代码实现：递归图解：

int maxDepth(TreeNode* root) {
		if (root == nullptr) return 0;
		return max(maxDepth(root->left), maxDepth(root->right)) + 1;
	}

对树不熟悉的其实完整的代码为：

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftDepth = getDepth(node->left);       // 左
        int rightDepth = getDepth(node->right);     // 右
        int depth = 1 + max(leftDepth, rightDepth); // 中
        return depth;
    }
    int maxDepth(TreeNode* root) {
        return getDepth(root);
    }
};

二叉树的最小深度：

看完了最大深度之后，再来看最小深度，第一次写很容易写成

int maxDepth(TreeNode* root) {
		if (root == nullptr) return 0;
		return max(maxDepth(root->left), maxDepth(root->right)) + 1;
	}

但是这是不对滴。

看题目，题目的最小深度的定义为：最小深度是从根节点到最近叶子节点的路径上的节点数量。

上方的写法如果一棵树的左孩子为空，只有右孩子时，此时的最小深度并不是1，而是右子树的最小深度。

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right != NULL) {//左子树为空，右子树不空时
            return 1 + minDepth(root->right);//返回的是右子树的最小深度
        }
        if (root->left != NULL && root->right == NULL) {//左子树不为空，右子树为空
            return 1 + minDepth(root->left);//返回的是左子树上最小深度
        }
        return 1 + min(minDepth(root->left), minDepth(root->right));//左右子树都不空时，返回左右子树其中的最小值。
    }
};

最终代码：

代码实现：

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<queue>
#include<set>
#include<cstring>
#include<functional>
using namespace std;
struct TreeNode

{

	int val;

	TreeNode *left;

	TreeNode *right;

	TreeNode() : val(0), left(NULL), right(NULL) {}

	TreeNode(int x) : val(x), left(NULL), right(NULL) {}

	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};
class Solution {
public:
	double maxDepth(TreeNode* root) {
		if (root == nullptr) return 0;
		return max(maxDepth(root->left), maxDepth(root->right)) + 1;
	}
	int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right != NULL) {//左子树为空，右子树不空时
            return 1 + minDepth(root->right);//返回的是右子树的最小深度
        }
        if (root->left != NULL && root->right == NULL) {//左子树不为空，右子树为空
            return 1 + minDepth(root->left);//返回的是左子树上最小深度
        }
        return 1 + min(minDepth(root->left), minDepth(root->right));//左右子树都不空时，返回左右子树其中的最小值。
    }

	double aveDepth(TreeNode* root) {
		double res;
		res = (maxDepth(root) + minDepth(root)) / 2;
		return res;
	}
};

TreeNode* inputTree()

{

	int n, count = 0;

	char item[100];

	cin >> n;

	if (n == 0)

		return NULL;



	cin >> item;

	TreeNode* root = new TreeNode(atoi(item));

	count++;

	queue<TreeNode*> nodeQueue;

	nodeQueue.push(root);



	while (count<n)

	{

		TreeNode* node = nodeQueue.front();

		nodeQueue.pop();



		cin >> item;

		count++;

		if (strcmp(item, "null") != 0)

		{

			int leftNumber = atoi(item);

			node->left = new TreeNode(leftNumber);

			nodeQueue.push(node->left);

		}



		if (count == n)

			break;



		cin >> item;

		count++;

		if (strcmp(item, "null") != 0)

		{

			int rightNumber = atoi(item);

			node->right = new TreeNode(rightNumber);

			nodeQueue.push(node->right);

		}

	}

	return root;

}

int main()

{

	TreeNode* root;

	root = inputTree();

	double res = Solution().aveDepth(root);

	cout << res;
	getchar();
	getchar();
}