leetcode第257题（简单）

原链接：https://leetcode-cn.com/problems/binary-tree-paths/

题目描述

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1
 /   \
2     3
 \
  5

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

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

解题思路

递归得方式遍历二叉树（深度优先搜索），如果是叶子节点就输出从根节点到当前叶子节点多经过的所有节点。递归过程可以用一个栈记录当前经过的所有节点。

代码（java）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        LinkedList<Integer> linkedList=new LinkedList<>();
        dfs(root,linkedList);
        return li;
    }

   private List<String> li=new ArrayList<>();
    public void dfs(TreeNode node, LinkedList<Integer> list){
        if(node.right==null&&node.left==null){
            StringBuilder builder=new StringBuilder();
            boolean b=true;
            for (Integer integer : list) {
                if(b){
                    b=!b;
                    builder.append(integer);
                }else{
                    builder.append("->").append(integer);
                }
            }
            if(list.size()==0){
                builder.append(node.val);
            }else{
                builder.append("->").append(node.val);
            }
            li.add(builder.toString());
        }else{
            if(node.left!=null){
                list.addLast(node.val);
                dfs(node.left,list);
                list.removeLast();
            }
            if(node.right!=null){
                list.addLast(node.val);
                dfs(node.right,list);
                list.removeLast();
            }
        }
    }
}