今天介绍的内容是 —— 树结构的深度优先搜索
按照惯例先来一个栗子，看图说话
黑色的字母是我们树的节点总共有11个，深度优先搜索的顺序是从根节点往左子树的开始，直到搜索到左子树的叶子节点， 然后搜索右子树的。
最终我们图片中的例子，经过深度优先搜索之后长这样[ A B E F I J C D G K H ]
深度优先搜索
那我们是怎么做到的呢？
深度优先搜索借助的栈这个结构：
这里先简述一下栈这个结构，栈是先进后出的，就行手枪弹夹一样，我们先放进去得子弹是最后打出来的。
解题思路：
我们先将根节点放进我们的栈中，然后取出之后，将它的子节点从右到左的放进去，如上图所示我们就是先放入 D， 再放入C，再放入B，然后我们再取出B再放入B的子节点，记住是从右到左！这样以此类推，直到我们的栈为空了我们就遍历完了所有树种的元素。
入栈和出栈模拟图
时间复杂度和空间复杂度分析：
时间复杂度是O(v + e) ：
和之前介绍的广度优先搜索一样，v代表是叶子节点的个数，e代表是edge就是连接节点和节点之间的连线。一个节点有3个连线就说明它有三个节点。因为我们需要遍历树中的所有节点O(v)，同时我们需要将它所有的子节点都加入栈中O(e)。所以我们最终的时间复杂度是O(v + e)
空间复杂度是O(v)：
和之前介绍的广度优先搜索一样，当树结构中有v个节点，但是只有1个根节点和 v - 1 个子节点，这时候压栈的时候就需要将所有的子节点放入进去。所以栈中需要存储 v - 1 数量的子节点，所以空间复杂度是 O(v)。
接下来我们看代码：
按照惯例是无注释加有注释的：
有注释版本
无注释版本
无注释版本
如果大家喜欢我的分享可以点一下喜欢谢谢！
