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

帽子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;
}