帽子zhzhC++dadasort> 最基础的二叉树遍历的问题，求最大深度。
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.
二叉树都忘了，有点淡淡的忧桑
从这道题开始就初涉图论的内容了，最基本的二叉树，又是最基本的遍历。但是想一想，若是没有这道题，我还永远忘了呢！待我想起遍历大法，看二叉树尸横遍野吧。
二叉树基础包括深度优先搜索、广度优先搜索，最大/最小深度，最大/最小广度，涉及递归。初步感觉对于二叉树掌握这几个就基本够了。
递归，好久不见
每逢我看到递归，都有点望而生畏。但至少就这道题来说，即使自己脑容量的内存和CPU不够，不能跟着递归深思熟虑，但递归确实是最容易用“第六感”去解决问题的办法。“反正我解决不了的让我的孩子去解决”，我想这就是递归的精髓吧~
用递归求二叉树最大深度
请看带注释的代码（今天因为注释详细被夸了@-@）
2016-07-18 00:04:10
/**
* 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) return 0; //0的情况，到叶子节点了。
int leftdepth = maxDepth(root -> left) + 1;//左侧来源的深度
int rightdepth = maxDepth(root -> right) + 1;//右侧来源的深度
return max(leftdepth,rightdepth);//返回该节点左右最大值
}
};
运行时间8ms。似乎还有更快的办法。
神奇的栈，非递归方法
当年学过数据结构，也还给老师很多了。欠缺砸实。
栈，我就没擅用过
“采用二叉树的后序遍历非递归算法。由于后序遍历非递归算法使用一个栈实现，每次都会在一条路径上走到最底层才向上访问，再向右访问。因此，记录下栈在遍历中的最大值，即为二叉树的最大深度。”
先贴一段博客园的代码学习学习：
#include <iostream>
#include <stack>
using namespace std;
typedef struct BinTree
{
int data;
BinTree *lc;
BinTree *rc;
}BTNode,*BinTree;
int max(int a,int b)
{
return (a>b)?a:b;
}
int BinTreeDepth(BinTree T)
{
stack<BinTree> s;
BinTree p = T,r = NULL;
int depth=0;
while(p||!s.empty())
{
if(p)
{ //从根节点向左边走
s.push(p);
int size = s.size();//获取栈的大小
depth = max(depth,size);//替换最大值
p = p->lc;
}
else
{ //左边走不通向右走
p = s.top();
if(p->rc&&p->rc!=r)//如果右子树存在，且未被访问过
{
p = p->rc;
s.push(p);
int size = s.size();//获取栈的大小
depth = max(depth,size);//替换最大值
p = p->lc;
}else
{
p=s.top();
s.pop();
cout<<p->data<<endl;
r=p; //记录最近访问的节点
p=NULL; //节点访问完之后，重置p指针,目的是为了防止再次将左孩子压栈
}
}
}
return depth;
}
