二叉树的所有路径 Posted on 2021-06-18 00:00:00 2021-06-26 00:00:00 by Author 摘要 给一颗二叉树，你能找出这颗二叉树的所有路径吗？？？？？？ # 二叉树得所有路径 1. 题目描述 - 给定一个二叉树，返回所有从根节点到叶子节点的路径。**说明:** 叶子节点是指没有子节点的节点。 2. 示例描述 - 示例一 - 输入：[1,null,2,null,null,3,null]  - 输出：["1->2->3"] - 示例二 - 输入：[1,null,2,3,6,7,8,9,null]  - 输出：["1->2->3->7","1->2->3->8","1->2->6->9"] 3. 解题思路 - 对于这道题来说，看起来比较难，但是细细想一想，还是比较简单得，为什么这么说尼，我们可以知道这道题目就是一道二叉树得遍历问题，只不过，在遍历过程中记录遍历得节点罢了，那么首先判断遍历是前中后序遍历得哪一种，不用想，肯定是前序遍历，英文路劲就是从根路径一直访问到叶子节点，这符合前序遍历得特点。所以使用前序遍历。那么怎么记录访问得路径尼，这里用一个集合记录已经访问得路径，当该节点是叶子节点得时候，那么集合中就存得是该二叉树得一条路径，就加入最终结果集合中。然后递归访问其他节点，只要遇到是根节点，就加入结果集和中，那么前序遍历完成那么整棵树得路径也就找完了。 - 但是在这过程中，需要使用到回溯的思想。因为我们知道一个二叉树的分支不止一条路径，那么在找到一条路径的时候，我们还需要寻找该分支下其他的路径，而这里的集合存放当前叶子节点的路径，假如另一条路径是该叶子节点的兄弟节点，那么他们父节点一样，我们已经找到该叶子节点的路径，结果集中在最后加入了该叶子节点，但是我们还要找其兄弟节点路径，那么该叶子节点就要从结果集中删除，然后继续访问其他叶子节点，这样就能达到回溯的效果。也能正确的寻找所有叶子节点的路径了。 - 具体代码如下所示。 4. 代码实现 ```java //最终结果集合 List<String> result = new ArrayList<>(); //在前序遍历中临时使用到的集合遍历 List<Integer> temp = new ArrayList<>(); public List<String> binaryTreePaths(TreeNode root) { //调用前序遍历的方法 visitTree(root, temp); return result; } public void visitTree(TreeNode node, List<Integer> temp) { //前序遍历的一般写法 if (node != null) { //如果访问的节点不为空，那么就记录遍历的路径 //即加入到前序遍历所走过的集合中 temp.add(node.val); //如果找到叶子节点 //那么就把这条路径加入最终结果集合中 if(node.right == null && node.left ==null){ //加入到结果集中 //调用的listTransferString方法是为了 //在leetcode上AC题目的时候保证输出的形式上一样 result.add(listTransferString(temp)); } //前序遍历的一般写法 visitTree(node.left, temp); visitTree(node.right, temp); //这一步比较重要 //这就是本题回溯的地方 //因为已经找到该叶子节点了，而结果集合中已经加入该叶子节点，叶子节点后肯定没有路径了， //而结果集合中有其他叶子节点的父节点，所以我们要回溯到 //与该叶子节点公用的父节点位置，也就是后退到该叶子节点父节点位置，以便找到其他的叶子节点的路径 //因为该叶子节点的父节点，不一定只有该叶子节点一条路径，还有其他的路径，所以要回溯 temp.remove(temp.size()-1); } } //这个方法就是把list集合转化成字符串形式 //为了与leetcode的结果一样，而单独写了一个方法 public String listTransferString(List<Integer> temp) { String str = ""; //遍历本次路径的结果集 for (int i = 0; i < temp.size(); i++) { //如果到最后一个节点，那么后面没有其他的节点，就没有“->”符号了 if (i == temp.size() - 1) { str += temp.get(i); } //否则就转换成我们需要的字符串形式 else str += temp.get(i) + "->"; } //最后放回构造好的字符串 return str; } ```
{{ item.content }}
{{ child.content }}