Leetcode/G家F家苹果-- 257. Binary Tree Paths(DFS)

257. Binary Tree Paths(dfs)

Easy

https://leetcode.com/problems/binary-tree-paths/

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

 Google Apple Facebook

思路： use dfs to traverse tree, append val to stringbuilder, add string to res when meeting root.
Complexity: Time: O(n), Space: O(n) -arraylist
way1 - stringbuilder

public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        helper(root, res, new StringBuilder());
        return res;
    }
    public void helper(TreeNode root, List<String> res, StringBuilder s){
        if(root == null)return;
        int len = s.length();
        s.append(root.val).append("->");
        if(root.left == null && root.right == null){
            res.add(s.toString().substring(0, s.length()-2));//remove last "->"
        }
        helper(root.left, res, s);
        helper(root.right, res, s);
        s.setLength(len);
    }

way2 - string

public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<String> ();
        if(root == null){ return res;}
        String cur = new String("");
        addpath(root, res, cur);
        return res;
    }
    private void addpath(TreeNode root,List<String> res,String cur){
        if(root == null){
            return;
        }
        cur += Integer.toString(root.val);
        cur += "->";//string + opperation no need to set back length
        if(root.left==null&&root.right==null){
            cur = cur.substring(0,cur.length()-2);
            res.add(cur);
        }
        addpath(root.left,res,cur);
        addpath(root.right,res,cur);
    }