[LeetCode]104. Maximum Depth of Binary Tree--二叉树的最大深度

时间:2021-02-06 17:29:47

104. 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.


/* 解法一:深度优先遍历(Depth-first-search)
* 简洁的递归解法,选择深度较大的子树的长度+1
* 即为整体二叉树的最大深度,依次递归调用即可
*
* 时间复杂度:O(n);空间复杂度:O(lgn)
* 解法一实现版本:
* 1.递归实现
* 2.递归实现--一行代码(好玩而已)
* 3.迭代实现--后序遍历
*/


/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/


// 1.递归实现
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL)
return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};

// 2.递归实现--一行代码
class Solution {
public:
int maxDepth(TreeNode* root) {
return root == NULL ? 0 : max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

// 3.迭代实现--后序遍历
class Solution {
public:
int maxDepth(TreeNode* root) {
// 后序遍历存储结点的临时栈 其最大长度就是二叉树的最大深度

int result = 0;
if(!root)
return result;
stack<TreeNode*> s;
// pCur:当前访问节点,pLastVisit:上次访问节点
TreeNode* pCur = root;
TreeNode* pLastVisit = NULL;
// 走到最左端
while(pCur){
s.push(pCur);
pCur = pCur->left;
}
while(!s.empty()){
result = max(result, int(s.size()));
pCur = s.top();
s.pop();
// 一个根节点被访问的前提是:无右子树或右子树已被访问过
if(pCur->right == NULL || pCur->right == pLastVisit){
pLastVisit = pCur;
}else{
// 根节点再次入栈
s.push(pCur);
//进入右子树,且可肯定右子树一定不为空
pCur = pCur->right;
while(pCur){
s.push(pCur);
pCur = pCur->left;
}
}
}
return result;
}
};

/** 解法二:宽度优先遍历(Breadth-first-search)
* 其实就是二叉树的层序遍历,有几层,最大深度就是多少
*/

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL)
return 0;

int result = 0;
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
++ result;
for(int i = 0, n = q.size(); i < n; ++ i)
{
TreeNode *p = q.front();
q.pop();

if(p->left != NULL)
q.push(p -> left);
if(p->right != NULL)
q.push(p -> right);
}
}

return result;
}
};