二叉树的遍历算法 概述
二叉树作为一个基础的数据结构，遍历算法作为一个基础的算法，两者结合当然是经典的组合了。很多题目都会有 ta 的身影，有直接问二叉树的遍历的，有间接问的。比如要你找到树中满足条件的节点，就是间接考察树的遍历，因为你要找到树中满足条件的点，就需要进行遍历。
你如果掌握了二叉树的遍历，那么也许其他复杂的树对于你来说也并不遥远了
二叉数的遍历主要有前中后遍历和层次遍历。 前中后属于 DFS，层次遍历属于 BFS。 DFS 和 BFS 都有着自己的应用，比如 leetcode 301 号问题和 609 号问题。
DFS 都可以使用栈来简化操作，并且其实树本身是一种递归的数据结构，因此递归和栈对于 DFS 来说是两个关键点。
DFS 图解：
(图片来自 )
BFS 的关键点在于如何记录每一层次是否遍历完成， 我们可以用一个标识位来表式当前层的结束。
首先不管是前中还是后序遍历，变的只是根节点的位置， 左右节点的顺序永远是先左后右。 比如前序遍历就是根在前面，即根左右。中序就是根在中间，即左根右。后序就是根在后面，即左右根。
下面我们依次讲解：
前序遍历相关问题144.binary-tree-preorder-traversal
前序遍历的顺序是根-左-右
思路是：
先将根结点入栈
出栈一个元素，将右节点和左节点依次入栈
重复 2 的步骤
code
py
class Solution(object): def preorderTraversal(self, root): if not root:return [] stack, res = [root], [] while stack: root = stack.pop() if root: res.append(root.val) if root.right: stack.append(root.right) if root.left: stack.append(root.left) return res