二叉树 ​

遍历核心框架

void traverse(TreeNode root) {
    if(root==null)return;
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

• 前序是刚进入一个节点，对左右子树一无所知，可以通过参数的形式影响左右子树的递归，只能拿到父节点传入参数

• 中序是递归完左子树，还没开始递归右子树的阶段，可以通过参数影响右子树的递归，且可以拿到左子树的参数，父节点传入参数和返回值

• 后序是递归完左右子树，离开节点向上的阶段，不能影响，且可以拿到左右子树的参数，父节点传入参数和返回值

在3个位置return以实现选择不同的遍历方案。

二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。

二叉树的最大深度 ​

每进入一个节点，dep++，每离开一个节点dep--，可以得到每一个节点的深度，保存最大值即可

二叉树的直径 ​

分别算出每一个节点的左右子树最大深度之和，保存最大值即为二叉树的直径。

利用后序遍历可以拿到左右子树最大深度之和。