BinaryTreePaths2 [source code]

public class BinaryTreePaths2 {
static
/******************************************************************************/
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        if (root == null) return res;
        dfs(root, res, sb);
        return res;
    }

    private void dfs(TreeNode root, List<String> ls, StringBuilder accum) {
        if (root == null) return;
        accum.append((accum.length() == 0 ? "" : "->") + root.val);
        int len = accum.length();
        if (root.left == null && root.right == null) {
            ls.add(accum.toString());
            return;
        }
        dfs(root.left, ls, accum);
        accum.setLength(len);
        dfs(root.right, ls, accum);
        accum.setLength(len);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        BinaryTreePaths2.Solution tester = new BinaryTreePaths2.Solution();
    }
}

这个是尝试用 StringBuilder来完成加速的一个版本, 使用 accum(with mutability)来完成 tag 的要点就是注意最后exit subtree的时候要有一个undone changes的操作. 最后的速度是18(51), 并没有完成加速, 这个有点奇怪;

Problem Description

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"]
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:37.75%
Contributor: LeetCode
Companies
google apple facebook
Related Topics
tree depth-first search
Similar Questions
Path Sum II