题目如下：
已知一个二叉树，指针pRoot指向根节点，求此二叉树的最大深度
关键点：
- 方法1：递归算法
- 原理：每一颗树的最大深度都是左右子树中的最大深度再加1
- 优点：代码行数非常少，易读性强
- 缺点：每一次递归调用增加额外的函数调用，新增栈帧空间，易造成stackoverflow的错误，效率低
- 方法2：深度优先（DFS）或广度优先（BFS），遍历二叉树，同时求得最大深度
- 深度优先遍历（DFS）：利用栈。深度优先遍历又分为前序（根-左-右），中序（左-根-右），后序（左-右-根）3类，这里采用较为简单的前序遍历。同时注意新建一个结构体，保存每个节点的层深，是一个较简单的方法
- 广度优先遍历（BFS）：利用队列，逐层遍历
代码实现：
// 前提：定义二叉树节点的数据结构
struct {
int key;
TreeNode* left;
TreeNode* right;
} TreeNode;
- 递归算法
int getTreeDepth(TreeNode* pRoot) {
if (null == pRoot) {
return 0;
}
return max(getTreeDepth(pRoot->left), getTreeDepth(pRoot->right)) + 1);
}
- 深度优先遍历算法（利用栈，前序遍历，顺序：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);
}
}
}
- 广度优先遍历算法
这里暂不实现。
作者：kevin song，2018.11.25于南京建邺区
