LeetCode: Maximum Depth of Binary Tree

LeetCode: Maximum Depth of Binary Tree

题目如下：

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 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，递归算法虽然代码简洁，思路清晰，但是在一定程度上消耗比较大。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。