手把手搞懂二叉树的递归与动态规划思维

遇到二叉树问题，不要直接盲目写递归，先问自己两个核心问题：

1. 是否可以通过遍历一遍二叉树得到答案？（对应回溯算法思维，前中后序位置写逻辑）
2. 是否可以定义一个递归函数，通过子问题答案推导原问题答案？（对应动态规划思维，依赖子树返回值）

1. 思维一：遍历思维代码模板

void traverse(TreeNode root) {
    if (root == null) return;
    // 前序位置 (刚进入节点)
    traverse(root.left);
    // 中序位置 (左子树遍历完)
    traverse(root.right);
    // 后序位置 (即将离开节点)
}

2. 思维二：分解问题思维代码模板

// 定义：输入一棵二叉树，返回这棵二叉树的最大深度
int maxDepth(TreeNode root) {
    if (root == null) return 0;
    // 利用子树的最大深度推导原树的最大深度
    int leftMax = maxDepth(root.left);
    int rightMax = maxDepth(root.right);
    return Math.max(leftMax, rightMax) + 1;
}