categories: [Blog,Algorithm]

257. 二叉树的所有路径

难度简单454
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:

1
/ \
2 3
\
5

输出: [“1->2->5”, “1->3”]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3.

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public List<String> binaryTreePaths(TreeNode root) {
  18.         List<String> paths = new ArrayList<String>();
  19.         if (root == null) {
  20.             return paths;
  21.         }
  22.         Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
  23.         Queue<String> pathQueue = new LinkedList<String>();
  25.         nodeQueue.offer(root);
  26.         pathQueue.offer(Integer.toString(root.val));
  28.         while (!nodeQueue.isEmpty()) {
  29.             TreeNode node = nodeQueue.poll(); 
  30.             String path = pathQueue.poll();
  32.             if (node.left == null && node.right == null) {
  33.                 paths.add(path);
  34.             } else {
  35.                 if (node.left != null) {
  36.                     nodeQueue.offer(node.left);
  37.                     pathQueue.offer(new StringBuffer(path).append("->").append(node.left.val).toString());
  38.                 }
  40.                 if (node.right != null) {
  41.                     nodeQueue.offer(node.right);
  42.                     pathQueue.offer(new StringBuffer(path).append("->").append(node.right.val).toString());
  43.                 }
  44.             }
  45.         }
  46.         return paths;
  47.     }

深度优先搜索

思路与算法

最直观的方法是使用深度优先搜索。在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点。

如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。
如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可。
如此，当遍历完整棵二叉树以后我们就得到了所有从根节点到叶子节点的路径。当然，深度优先搜索也可以使用非递归的方式实现，这里不再赘述。

广度优先搜索

思路与算法

我们也可以用广度优先搜索来实现。我们维护一个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中，我们取出队列中的首节点，如果它是叶子节点，则将它对应的路径加入到答案中。如果它不是叶子节点，则将它的所有孩子节点加入到队列的末尾。当队列为空时广度优先搜索结束，我们即能得到答案。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode-solution/

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public List<String> binaryTreePaths(TreeNode root) {
  18.         List<String> paths = new ArrayList<String>();
  19.         constructPaths(root, "", paths);
  20.         return paths;
  21.     }
  23.     public void constructPaths(TreeNode root, String path, List<String> paths) {
  24.         if (root != null) {
  25.             StringBuffer pathSB = new StringBuffer(path);
  26.             pathSB.append(Integer.toString(root.val));
  27.             if (root.left == null && root.right == null) {  // 当前节点是叶子节点
  28.                 paths.add(pathSB.toString());  // 把路径加入到答案中
  29.             } else {
  30.                 pathSB.append("->");  // 当前节点不是叶子节点，继续递归遍历
  31.                 constructPaths(root.left, pathSB.toString(), paths);
  32.                 constructPaths(root.right, pathSB.toString(), paths);
  33.             }
  34.         }
  35.     }
  38. //作者：LeetCode-Solution
  39. //链接：https://leetcode-cn.com/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode-solution/
  41. }