LeetCode - 257. Binary Tree Paths

这道题目和前面的Path Sum, Path Sum II, Combination Sum, Combination Sum II, Subsets, Subsets II题目的思路和做法是一样的，需要放在一起多看。但是这道题目与前面不同有一个不太一样的地方，在递归函数中的结尾，只要把前面加进来的一个元素删除就可以了，但是这道题目不仅需要加入元素，还需要加入->，所以删除的方法也不太一样，只要使用StringBuilder的setLength()方法保持原来的长度即可。时间复杂度为O(n)，因为这个算法的本质是遍历所有的节点，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution { 
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new LinkedList<String>();
        StringBuilder sb = new StringBuilder();
        findTreePaths(root, result, sb);
        return result;
    }
    
    private void findTreePaths(TreeNode root, List<String> result, StringBuilder sb){
        if(root == null) return;
        
        int length = sb.length();
        sb.append(root.val);
        if(root.left == null && root.right == null){
            result.add(sb.toString());
        }else{
            sb.append("->");
            findTreePaths(root.left, result, sb);
            findTreePaths(root.right, result, sb);
        }
        sb.setLength(length);       // don't forget to remove element
    }
}
           

知识点：

1. 注意在遇到String问题的时候，可以多考虑使用StringBuilder，这样相对于String的+来说会更加高效