二叉树

二叉树模板

每一道二叉树数都可以用一下思维模式来解决，二叉树解题的思维模式分两类：
1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。ps：可以用于回溯算法.
2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。ps：可以用于动态规划.

总结：
二叉树的所有问题，都是让你在前中后位序位置（when）写下代码，只需思考当前节点一个做什么（what）

模块代码体现：

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