二叉树解题思路小记

二叉树前中后序位置

代码框架

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

代码写在不同的位置，只是执行的时间不同。

前序位置

刚刚进入二叉树节点的时候执行前序位置的代码。例如前序遍历的时候，先把当前节点添加到集合中，再处理左右子树节点。

中序位置

一般是指当前节点的左子树节点处理完以后，右子树处理前的时候执行的代码。例如中序遍历的时候，处理左子树节点，再添加当前节点到集合中。

后序位置

左右子树处理完成以后，离开当前节点的时候执行。例如后序遍历的时候，先把左右子树节点处理完，再添加当前节点到集合中。

前序和后序的异同点

• 前序位置的代码执行可以理解为是自顶向下的，后序位置的代码执行是自底向上的
• 前序位置的代码只能从函数参数中获取父节点传递的数据，后序位置的代码不仅可以获取参数数据，还可以获取的子树通过函数返回值传递回来的数据。

二叉树解题思路

解题思路有两种：第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案

在当前节点处理，依次往子树递归，在叶子节点获得结果，这是遍历一遍二叉树得出答案。代码逻辑主要集中在前序位置。

二叉树当前节点的结果，在左右子树的结果上产生，这就是分解问题计算答案的思路。代码逻辑主要集中在后序位置。

解题思考过程

1. 是否可以通过遍历一遍二叉树得到答案？如果不能的话，是否可以定义一个递归函数，通过一个子问题（子树）的答案推导出原问题的答案。
2. 一旦发现题目和子树有关，大概率要给函数设置合理的定义和返回值，在后续位置写代码。

参考

labuladong.gitee.io/algo/1/7/