算法复习-二叉树

二叉树解题的思维模式分两类：

1、是否可以通过遍历一遍，拿信息/做操作，得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，思考这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。（类似 DP）

无论使用哪种思维模式，都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？
需要在什么时候（前/中/后序位置）做？
其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

序列化处理IO

三种遍历位置

但是我想说，前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点，绝不仅仅是三个顺序不同的 List：

前序位置的代码在刚刚进入一个二叉树节点的时候执行；
后序位置的代码在将要离开一个二叉树节点的时候执行；
中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。
后序位置的代码最强，不仅可以获取参数数据，还可以同时获取到左右子树通过函数返回值传递回来的数据。

111. 二叉树的最小深度

维护深度，在前序位置 $\text{depth}++$，后序位置 $\text{depth}–$，（因为前序位置是进入一个节点的时候，后序位置是离开一个节点的时候）当遇到叶子节点时更新答案。

101. 对称二叉树

判断一棵树是否对称→判断两棵树是否为对称的。判断 $A$ 子树的左子树和 $B$ 子树的右子树是否相同，$A$ 子树的右子树和 $B$ 子树的左子树是否相同…

110. 平衡二叉树

用一次后序遍历同时得到“高度”和“是否不平衡”。
约定 dfs 返回值：$\geq 0$ 表示子树高度，$-1$ 表示该子树不平衡并向上短路。
访问顺序：先递归拿到左子树高度，再拿右子树高度，然后比较差值并计算当前高度。这样不会重复计算高度，后序遍历位置获取左右子树的高度，判断是否平衡，更新答案。

层序遍历

记住维护深度（按层分）。可以解决分层/深度相关的问题。每层记录队列当前大小，存入一个 vector<int> level，最后存入结果 vector<vector<int>> ans

void levelOrder(TreeNode* root) {
  vector<vector<int>> res;
  if(!root) return res;
  queue<TreeNode*> q;
  q.push(root);
  while(!q.empty()){
    int size = q.size(); // 记录当时队列的大小，即为当前层的节点数
    vector<int> level;
    for(int i = 0; i < size; i++){
      TreeNode* node = q.front();
      q.pop();
      level.push_back(node->val);
      if(node->left) q.push(node->left);
      if(node->right) q.push(node->right);
    }
    res.push_back(level);
  }
  return res;
}