LeetCode: Maximum Depth of Binary Tree

桃扇骨 2022-08-06 09:13 32阅读 0赞

题目如下：

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

即求二叉树的（最大）深度。

有两种思路：一是使用递归，二是使用二叉树层序遍历。

递归算法：用递归的函数，返回左子树或者右子树中大的深度加1，作为自己的深度。

int maxDepth(TreeNode *root)
    {
    	if (root == NULL) return 0;
    	int left = maxDepth1(root->left);
    	int right = maxDepth1(root->right);
    	return left > right ? left + 1 : right + 1;
    }

二叉树的层序遍历使用队列将节点依次存储，每一个出列一个节点，当一层节点完全出列的时候，深度加1。

int maxDepth(TreeNode *root)
    {
    	if (root == NULL) return 0;
    	queue<TreeNode *>  btQueue;//使用队列进行层序遍历
    	btQueue.push(root);
    	int count = 1;//记录当前层的节点个数
    	int depth = 0;//记录当前遍历的深度
    	while (!btQueue.empty())
    	{
    		TreeNode *currentNode = btQueue.front();
    		btQueue.pop();//每次循环出队一个节点
    		count--;
    
    		if (currentNode->left) btQueue.push(currentNode->left);
    		if (currentNode->right) btQueue.push(currentNode->right);
    
    		if (count == 0)
    		{
    			//每当遍历完上一次节点的时候，层数depth++，count修改为现在队列中的元素个数，即下层的节点个数
    			depth++;
    			count = btQueue.size();
    		}
    	}
    	return depth;
    }

在Leetcode上进行提交，递归算法的运行时间为22ms，非递归的层序遍历算法为14ms，递归算法虽然代码简洁，思路清晰，但是在一定程度上消耗比较大。