帽子zhzhC++dadasort> 最基礎(chǔ)的二叉樹遍歷的問題，求最大深度黎棠。
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.
二叉樹都忘了掌呜，有點淡淡的憂桑
從這道題開始就初涉圖論的內(nèi)容了大刊，最基本的二叉樹，又是最基本的遍歷。但是想一想伟墙，若是沒有這道題钳吟，我還永遠忘了呢！待我想起遍歷大法贴见，看二叉樹尸橫遍野吧烘苹。
二叉樹基礎(chǔ)包括深度優(yōu)先搜索、廣度優(yōu)先搜索蝇刀，最大/最小深度螟加，最大/最小廣度，涉及遞歸吞琐。初步感覺對于二叉樹掌握這幾個就基本夠了捆探。
遞歸，好久不見
每逢我看到遞歸站粟，都有點望而生畏黍图。但至少就這道題來說，即使自己腦容量的內(nèi)存和CPU不夠奴烙，不能跟著遞歸深思熟慮助被，但遞歸確實是最容易用“第六感”去解決問題的辦法∏芯鳎“反正我解決不了的讓我的孩子去解決”揩环，我想這就是遞歸的精髓吧~
用遞歸求二叉樹最大深度
請看帶注釋的代碼（今天因為注釋詳細(xì)被夸了@-@）
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的情況幅虑，到葉子節(jié)點了丰滑。
int leftdepth = maxDepth(root -> left) + 1;//左側(cè)來源的深度
int rightdepth = maxDepth(root -> right) + 1;//右側(cè)來源的深度
return max(leftdepth,rightdepth);//返回該節(jié)點左右最大值
}
};
運行時間8ms。似乎還有更快的辦法倒庵。
神奇的棧褒墨，非遞歸方法
當(dāng)年學(xué)過數(shù)據(jù)結(jié)構(gòu)炫刷，也還給老師很多了。欠缺砸實郁妈。
棧浑玛，我就沒擅用過
“采用二叉樹的后序遍歷非遞歸算法。由于后序遍歷非遞歸算法使用一個棧實現(xiàn)噩咪，每次都會在一條路徑上走到最底層才向上訪問顾彰，再向右訪問。因此剧腻，記錄下棧在遍歷中的最大值拘央，即為二叉樹的最大深度∈樵冢”
先貼一段博客園的代碼學(xué)習(xí)學(xué)習(xí)：
#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)
{ //從根節(jié)點向左邊走
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; //記錄最近訪問的節(jié)點
p=NULL; //節(jié)點訪問完之后，重置p指針,目的是為了防止再次將左孩子壓棧
}
}
}
return depth;
}
