最近看了labuladong讲二叉树，掌握了一种思路：
拿到二叉树题目，思考三个维度
——能不能遍历一遍就得出结果？ 如果可以，配合一个traverse函数+外部变量进行实现。
——能不能定义一个递归函数，用子问题（子树）推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值。
——无论使用哪一种思维模式，你都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做。
Leetcode 104.MaxDepth of Binary Tree 二叉树的最大深度
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
1.可以遍历一遍就得出结果，用一个traverse函数遍历该二叉树，输入root根结点即可。
设定一个记录max depth的外部遍历res, 以及每一遍走到叶子结点得到一个depth。
res就是从depth里面选择出来的最大值！最后输出res。
因此我们可以用一遍“遍历”来解这道题：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//res最大深度
int res = 0;
//depth当前结点深度
int depth = 0;
//主函数，求最大深度，输入根结点
public int maxDepth(TreeNode root) {
traverse(root);
return res;
}
//遍历函数，输入根结点
void traverse(TreeNode root) {
//corner case:结点是空，直接返回
if (root == null) {
return;
}
//前序位置：进入结点前先深度depth+1
depth++;
//判断是否是叶子结点，到了叶子结点再和res比较取较大值作为当前最大深度
if (root.left == null && root.right == null) {
res = Math.max(res, depth);
}
//遍历左子树
traverse(root.left);
//遍历右子树
traverse(root.right);
//后序位置：要离开结点所以需要深度depth-1
depth--;
}
}
python版本结合stack的思路：
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
res = 1
stack = [[root, 1]]
while stack:
node, depth = stack.pop()
if node:
res = max(res, depth)
stack.append([node.left, depth+1])
stack.append([node.right, depth+1])
return res
2.你也可以把这个问题拆解为：整个二叉树的最大深度=左右子树中的最大深度+1（根结点占据一层），用递归调用maxdepth.
maxDepth递归函数定义 输入root返回maxDepth
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root == None:
return 0
else:
leftMax = self.maxDepth(root.left)
rightMax = self.maxDepth(root.right)
res = max(leftMax,rightMax)+1
return res
3.第一种思路是：遍历一遍得到结果
每个节点需要在遍历进入前先记录它所在的深度（层数），因为不需要获取子树的信息所以其实很自然就是写在前序位置
检查是否是叶子结点：是就要记录此时的临时depth和res进行比较，取较大值
从最底层往上返回的时候要让层数-1
第二种思路：分解问题的思维
每个节点计算左右子树的最大深度+1
既然需要先计算出左右子树的最大深度，所以其实很自然的可以理解需要从底向上的后序遍历！
4.补充题解BFS解法
涉及到层数的用BFS都很合适
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
level = 0
q = deque([root])
while q:
for i in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
level += 1
return level
5.注意要熟练写的一些内容：
(1).corner case: python中只有None type没有null！
if root == None：
return 0
(2).traverse的思路：
def traverse(root):
res = []
res.append(root.val)
traverse(root.left)
traverse(root.right)
标签：Binary,right,TreeNode,res,depth,二叉树,left,root,MaxDepth From： https://www.cnblogs.com/cassiehao/p/17034050.html