LeetCode:104_Maximum Depth of Binary Tree | 二叉树的最大深度 | Easy

时间:2021-11-27 19:24:07

要求:求二叉树的深度(二叉树的深度为最远叶子节点到根节点的距离,即根节点到最远叶子节点的距离)

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.

有两种求解的思路,一种采用DFS的思想,一种采用BFS的思想,如下代码所示:

 struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(NULL),right(NULL) {}
}; //采用DFS的思想
int maxDepth(TreeNode *root)
{
if (NULL == root)
return ;
int l = maxDepth(root->left);
int r = maxDepth(root->right); return l > r ? l + :r+;
//以上这两种方式有一种更简便的方法
//return 1 + max(maxDepth(root->left), maxDepth(root->right));
} //采用BFS的方法,引入队列
int maxDepth(TreeNode *root)
{
if (NULL == root)
return ;
queue <TreeNode *> que;
int nCount = ;
int nDepth = ;// 记录队列里面每一层上的元素 que.push(root);
while(!que.empty()) {
TreeNode *pTemp = que.front();
que.pop();
nCount --; if (pTemp->left)
que.push(pTemp->left);
if (pTemp->right)
que.push(pTemp->right); if (nCount == ) {
nDepth ++;
nCount = que.size();
}
}
return nDepth;
}