二叉树：输出根节点到叶子的路径

    给定一个二叉树，输出从跟节点到所有叶子的路径。如下面的二叉树，输出路径的集合["1->2->5", "1->3"]。

    方法一：使用递归算法，把经过的路径作为参数往下传

public List<String> binaryTreePaths(TreeNode root) { LinkedList<String> result = new LinkedList<String>(); if(root == null) return result; getPath(root, result, root.val + ""); return result; } public void getPath(TreeNode root, LinkedList<String> result, String str){ if(root.left == null && root.right == null){ result.add(str); return; } if(root.left != null) getPath(root.left, result, str + "->" + root.left.val); if(root.right != null) getPath(root.right, result, str + "->" + root.right.val); }

    方法二：可以不用辅助函数，直接在路径集合上操作，把当前节点添加到下级返回的每一个路径上

public List<String> binaryTreePaths(TreeNode root) { List<String> paths = new LinkedList<>(); if(root == null) return paths; if(root.left == null && root.right == null){ paths.add(root.val+""); return paths; } for (String path : binaryTreePaths(root.left)) { paths.add(root.val + "->" + path); } for (String path : binaryTreePaths(root.right)) { paths.add(root.val + "->" + path); } return paths; }

    方法三：不用递归，而使用队列（BFS）或者栈（深度优先），维持节点和字符串两个队列（或栈），每访问一个节点，相应字符串进行同步更改

public List<String> binaryTreePaths(TreeNode root) { List<String> list=new ArrayList<String>(); Queue<TreeNode> qNode=new LinkedList<TreeNode>(); Queue<String> qStr=new LinkedList<String>(); if (root==null) return list; qNode.add(root); qStr.add(""); while(!qNode.isEmpty()) { TreeNode curNode=qNode.remove(); String curStr=qStr.remove(); if (curNode.left==null && curNode.right==null) list.add(curStr+curNode.val); if (curNode.left!=null) { qNode.add(curNode.left); qStr.add(curStr+curNode.val+"->"); } if (curNode.right!=null) { qNode.add(curNode.right); qStr.add(curStr+curNode.val+"->"); } } return list; }