题目如下：

已知一个二叉树，指针pRoot指向根节点，求此二叉树的最大深度

关键点：

• 方法1：递归算法
  • 原理：每一颗树的最大深度都是左右子树中的最大深度再加1
  • 优点：代码行数非常少，易读性强
  • 缺点：每一次递归调用增加额外的函数调用，新增栈帧空间，易造成stackoverflow的错误，效率低
• 方法2：深度优先（DFS）或广度优先（BFS），遍历二叉树，同时求得最大深度
  • 深度优先遍历（DFS）：利用栈。深度优先遍历又分为前序（根-左-右），中序（左-根-右），后序（左-右-根）3类，这里采用较为简单的前序遍历。同时注意新建一个结构体，保存每个节点的层深，是一个较简单的方法
  • 广度优先遍历（BFS）：利用队列，逐层遍历

代码实现：

// 前提：定义二叉树节点的数据结构
struct {
    int key;
    TreeNode* left;
    TreeNode* right;
} TreeNode;

1. 递归算法

int getTreeDepth(TreeNode* pRoot) {
    if (null == pRoot) {
        return 0;
    }

    return max(getTreeDepth(pRoot->left), getTreeDepth(pRoot->right)) + 1);
}

2. 深度优先遍历算法（利用栈，前序遍历，顺序：1-2-4-5-7-8-3-6，时间复杂度：O(n)，n为节点个数）

struct {
    int depth; //当前节点的深度
    TreeNode *node; // 当前节点
} NewTreeNode;

int getTreeDepth(TreeNode* pRoot) {
    int maxDepth = 0; // 记录最大深度
    if (null == pRoot) {
        return maxDepth;
    }

    // 这里先用伪代码，Stack类，有empty()，push()压栈，pop()出栈方法    
    Stack<NewTreeNode> stack = new Stack<NewTreeNode>();
    
    // 根节点入栈
    NewTreeNode rootNode = {1, pRoot};
    stack.push(rootNode);

    while(!stack.empty()) {
        NewTreeNode newNode = stack.pop();
        TreeNode *pLeft = newNode->node->left;
        TreeNode *pRight = newNode->node->right;        

        // 更新树的最大深度值
        maxDepth = newNode.depth > maxDepth ? newNode.depth : maxDepth;

        // 前序遍历，先压右，再压左
        if (null != pRight) {
            NewTreeNode rightNode = {newNode.depth + 1, pRight};
            stack.push(rightNode);
        }
        if (null != pLeft) {
            NewTreeNode leftNode = {newNode.depth + 1, pLeft};
            stack.push(leftNode);
        }
    }
}

3. 广度优先遍历算法
   这里暂不实现。

作者：kevin song，2018.11.25于南京建邺区