二叉树的遍历

深度优先搜索

前中后序遍历都是深度优先搜索

<aside> 💡

前 / 中 / 后序中的“序”指的是中间节点搜索的次序

• 前序：中-左-右
• 中序：左-中-右
• 后序：左-右-中

一般采用递归来实现，或使用栈来模拟递归进行实现

</aside>

广度优先搜索

即层序遍历

递归遍历

<aside> 💡

递归遍历的要点：

1. 确定递归函数的参数和返回值
2. 确定终止条件
3. 确定单层递归的逻辑 </aside>

<aside> 💡

递归的一些要点

1. 对于需要在递归过程中保持唯一性的变量（如最后的结果），可以使用引用维护（效果与使用一个全局变量维护相同）
2. 关于递归顺序：
   • 当子节点需要父节点信息的时候使用前序遍历，如：
     • 257子节点需要父节点路径
     • 404子节点需要父节点判断该子节点是不是左节点
   • 当父节点需要子节点信息时使用后序遍历，如：
     • 104求最大深度，父节点需要子节点的高度信息 </aside>

迭代遍历

<aside> 💡

迭代的一些要点：

• 当需要该节点除成员属性以外的信息（如节点路径，是否是左节点）时，可以多建几个栈同步保持节点信息
  • 257. 二叉树的所有路径中，多创建了一个栈来保持路径字符串 </aside>

二叉搜索树

<aside> 💡

二叉搜索树的一个重要性质：以中序遍历二叉树，得到的遍历序列一定是单调递增的

</aside>

题目

94. 二叉树的中序遍历

144. 二叉树的前序遍历

145. 二叉树的后序遍历

102. 二叉树的层序遍历

226. 翻转二叉树

101. 对称二叉树