257. Binary Tree Paths.md

257. Binary Tree Paths

Question

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

Note: A leaf is a node with no children.

Example:

Input:

   1
 /   \
2     3
 \
  5

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

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Thinking:

• Method 1:dfs

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if(root == null) return res;
        bfs(root, new StringBuilder(), res);
        return res;
    }
    private void bfs(TreeNode node, StringBuilder sb, List<String> res){
        if(node.left == null && node.right == null){
            sb.append(node.val);
            res.add(sb.toString());
            return;
        }else{
            sb.append(node.val + "->");
            if(node.left != null)   bfs(node.left, new StringBuilder(sb.toString()), res);
            if(node.right != null)   bfs(node.right, new StringBuilder(sb.toString()), res);
        }
    }
}

Second time

1. I still used bfs to solve this question. However, using list instead of StringBuilder is faster.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private String arrow = "->";
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new LinkedList<>();
        if(root == null) return result;
        addPath(result, new LinkedList<Integer>(), root);
        return result;
    }
    private void addPath(List<String> result, List<Integer> temp, TreeNode node){
        temp.add(node.val);
        if(node.left == null && node.right == null){
            if(temp.size() == 0) return;
            else if(temp.size() == 1){
                result.add("" + temp.get(0));
            }else{
                StringBuilder sb = new StringBuilder();
                sb.append(temp.get(0));
                for(int i = 1; i < temp.size(); i++){
                    sb.append(this.arrow);
                    sb.append(temp.get(i));
                }
                result.add(sb.toString());
            }
        }else{
            if(node.left != null){
                addPath(result, temp, node.left);
            }
            if(node.right != null){
                addPath(result, temp, node.right);
            }
        }
        temp.remove(temp.size() - 1);
    }
}

Third Time

• Method 1: dfs

   /**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */
   class Solution {
   	private List<String> result;
   	public List<String> binaryTreePaths(TreeNode root) {
   		this.result = new ArrayList<>();
   		if(root == null) return result;
   		if(root.left == null && root.right == null) result.add(root.val + "");
   		if(root.left != null) dfs(root.left, root.val + "");
   		if(root.right != null) dfs(root.right, root.val + "");
   		return result;
   	}
   	private void dfs(TreeNode node, String s){
   		String cur = s + "->" + node.val;
   		if(node.left == null && node.right == null) result.add(cur);
   		if(node.left != null) dfs(node.left, cur);
   		if(node.right != null) dfs(node.right, cur);
   	}
   }