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.
后序遍历二叉树思想/**
* Definition for binary tree* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include <stack>
class Solution {
public:
int maxDepth(TreeNode *root) {
if(root == NULL)
return 0;
std::stack<TreeNode*> node;
std::stack<int> tag;
int deep = 0;
TreeNode* pNode = root;
// node.push(pNode);
// tag.push(0);
// pNode = pNode->left;
while(pNode != NULL || node.size() != 0)
{
//pNode = node.top();
while(pNode != NULL)
{
node.push(pNode);
tag.push(0);
pNode = pNode->left;
}
if(!node.empty())
{
pNode = node.top();
if(tag.top() == 0)
{
tag.pop();
tag.push(1);
pNode = pNode->right;
}
else
{
deep = deep>node.size()? deep:node.size();
node.pop();
tag.pop();
pNode = NULL;
}
}
}
return deep;
}
};