黑芝麻嵌入式面试题及参考答案

请详细描述二叉树的深度优先搜索（dfs）流程。

深度优先搜索是一种用于遍历二叉树的重要算法，主要有先序遍历、中序遍历和后序遍历三种方式。

先序遍历的流程是，首先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。这就好比是在探索一个家族树，先拜访家族中的长辈（根节点），再去拜访长辈的左侧晚辈（左子树），最后拜访长辈的右侧晚辈（右子树）。比如对于二叉树的节点为 1（根）、2（左子树）、3（右子树），先序遍历的访问顺序就是 1 - 2 - 3。

中序遍历的过程是先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。用前面家族树的例子来解释，就是先拜访长辈左侧的晚辈，再拜访长辈，最后拜访长辈右侧的晚辈。对于上述二叉树节点，中序遍历顺序是 2 - 1 - 3。

后序遍历是先递归地遍历左子树，再递归地遍历右子树，最后访问根节点。还是以家族树为例，先拜访左右两侧的晚辈，最后拜访长辈。对于给定二叉树，后序遍历顺序是 2 - 3 - 1。

在实现深度优先搜索时，通常会使用递归的方式。以先序遍