多叉树全路径遍历
本文为原创作品，首发于微信公众号：【坂本先生】，如需转载请在文首明显位置标明“转载于微信公众号：【坂本先生】”，否则追究其法律责任。
微信文章地址：实战算法——多叉树全路径遍历
本文研究的是如何对一个多叉树进行全路径的遍历，并输出全路径结果。该问题的研究可以用在：Trie树中查看所有字典值这个问题上。本文将对该问题进行详细的模拟及进行代码实现，讨论了递归和非递归两种方法优劣并分别进行实现，如果读者对这两种方法的优劣不感兴趣可直接跳到问题构建章节进行阅读。文章较长，推荐大家先收藏再进行阅读。
文章目录
递归和非递归比较
这个问题知乎上已经有了很多答案（https://www.zhihu.com/question/20278387），在其基础上我进行了一波总结：
递归将一个问题分解为若干相对小一点的问题，遇到递归出口再原路返回，因此必须保存相关的中间值，这些中间值压入栈保存，问题规模较大时会占用大量内存。
非递归执行效率高，运行时间只因循环次数增加而增加，没什么额外开销。空间上没有什么增加
递归的劣势和优势 递归的劣势递归容易产生"栈溢出"错误（stack overflow）。因为需要同时保存成千上百个调用记录，所以递归非常耗费内存。
效率方面，递归可能存在冗余计算。使用递归的方式会有冗余计算（比如最典型的是斐波那契数列，计算第6个需要计算第4个和第5个，而计算第5个还需要计算第4个，所处会重复）。迭代在这方面有绝对优势。
递归的优势递归拥有较好的代码可读性，对于数据量不算太大的运算，使用递归算法绰绰有余。
问题构建现在存在一个多叉树，其结点情况如下图，需要给出方法将叶子节点的所有路径进行输出。
最终输出结果应该有5个，即[rad,rac,rbe,rbf,rg]
问题解决首先我们对结点进行分析，构建一个结点类（TreeNode），然后我们需要有一个树类（MultiTree），包含了全路径打印的方法。最后我们需要建立一个Main方法进行测试。最终的项目结构如下：
注意：本文使用了lombok注解，省去了get，set及相关方法的实现。如果读者没有使用过lombok也可以自己编写对应的get，set方法，后文会对每个类进行说明需要进行实现的方法，对核心代码没有影响。
TreeNode类
节点类，主要包含两个字段：
content：用于存储当前节点存储的内容
childs：用于存储子节点信息，HashMap的string存储的是子节点内容，childs采用HashMap实现有利于实现子节点快速查找
该类中包含了必要的get，set方法，一个无参构造器，一个全参构造器
@Data @RequiredArgsConstructor @AllArgsConstructor public class TreeNode { private String content; private HashMap<String,TreeNode> childs; }MultiTree类
包含的字段只有两个：
root：根节点
pathList：用于存储遍历过程中得到的路径
该类中的构造函数中我手动创建问题构建中的树，相关代码如下：
public MultiTree(){ //创建根节点 HashMap rootChilds = new HashMap(); this.root = new TreeNode("r",rootChilds); //第一层子节点 HashMap aChilds = new HashMap(); TreeNode aNode = new TreeNode("a",aChilds); HashMap bChilds = new HashMap(); TreeNode bNode = new TreeNode("b",bChilds); HashMap gChilds = new HashMap(); TreeNode gNode = new TreeNode("g",gChilds); //第二层结点 HashMap dChilds = new HashMap(); TreeNode dNode = new TreeNode("d",dChilds); HashMap cChilds = new HashMap(); TreeNode cNode = new TreeNode("c",cChilds); HashMap eChilds = new HashMap(); TreeNode eNode = new TreeNode("e",eChilds); HashMap fChilds = new HashMap(); TreeNode fNode = new TreeNode("f",fChilds); //建立结点联系 rootChilds.put("a",aNode); rootChilds.put("b",bNode); rootChilds.put("g",gNode); aChilds.put("d",dNode); aChilds.put("c",cNode); bChilds.put("e",eNode); bChilds.put("f",fNode); }