257. Binary Tree Paths

四刷 05/2022

Runtime: 1 ms, faster than 99.98% of Java online submissions for Binary Tree Paths.

Memory Usage: 43 MB, less than 63.99% of Java online submissions for Binary Tree Paths.

/**

 * 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) {

        List<String> result = new ArrayList<>();

        if (root == null) {

            return result;

        }

        dfs(root, result, new StringBuilder());

        return result;

    }

    private void dfs(TreeNode node, List<String> result, StringBuilder path) {

        if (node == null) {

            return;

        }

        int originalLen = path.length();

        if (originalLen != 0) {

            path.append("->");

        }

        path.append(node.val);

        // leaf node

        if (node.left == null && node.right == null) {

            result.add(path.toString());

            path.setLength(originalLen);

            return;

        }

        

        dfs(node.left, result, path);

        dfs(node.right, result, path);

        path.setLength(originalLen);

    }

}

3RD TRY
Bug Free~
94.85 %
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
if (root != null) {
dfs(root, new StringBuilder(), result);
}
return result;
}
private void dfs(TreeNode node, StringBuilder sb, List<String> result) {
// guarantee node is not null
int len = sb.length();
if (len != 0) {
sb.append("->");
}
sb.append(node.val);
if (node.left == null && node.right == null) {
result.add(sb.toString());
sb.setLength(len);
return;
}
if (node.left != null) {
dfs(node.left, sb, result);
}

if (node.right != null) {
dfs(node.right, sb, result);
}
sb.setLength(len);
}
}

写错并且要注意的地方很多
1.不能把root == null作为终止条件，因为在leaf的时候left,right会分别加入一次，这样会把同样的答案加两遍
2.所有递归的出口 无论是否成功都要backtracking
二刷
50.16 % 
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) return result;
        StringBuilder sb = new StringBuilder();
        dfsHelper(root, result, sb);
        return result;
    }
    private void dfsHelper(TreeNode root, List<String> result, StringBuilder sb) {
        int prevLen = sb.length();
        sb.append(root.val);
        // leaf
        if (root.left == null && root.right == null) { 
            result.add(sb.toString());
            sb.setLength(prevLen);
            return;
        }
        sb.append("->");
        // length after added ("rootVal->")
        prevLen = sb.length();
        if (root.left != null) {
            dfsHelper(root.left, result, sb);
            sb.setLength(prevLen);
        }
        if (root.right != null) {
            dfsHelper(root.right, result, sb);
            sb.setLength(prevLen);
        }
     
    }
}

一刷
43.30 %
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) return result;
        binaryTreePathsDfsHelper(root, new StringBuilder(), result);
        return result;
    }
    private void binaryTreePathsDfsHelper(TreeNode root, StringBuilder path, List<String> result) {
        int pathOriginalLength = path.length();
        if (root.left == null && root.right == null) {
            path.append(root.val);
            result.add(path.toString());
            path.delete(pathOriginalLength, path.length());
            return;
        }
     
        path.append(root.val + "->");
        if (root.left != null) {
            binaryTreePathsDfsHelper(root.left, path, result);
        }
        if (root.right != null) {
            binaryTreePathsDfsHelper(root.right, path, result);
        }
        path.delete(pathOriginalLength, path.length());
    }
}