Binary Tree Paths

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

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

Thoughts

看到返回所有的paths直接要想到dfs。 DFS用一个list保存当前path，在用一组list保存所有的paths。 需要注意的是每到一个新结点应新生成个path，否则都会在一个空间操作。

Code

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

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root != null) {
            dfs(root, "", res);
        }
        return res;
    }
}

Analysis

每个结点访问一遍，时间复杂度O(n). 但如果考虑到string 粘贴操作, O(N^2).

Ver.2

简单版 path sum II.

/**
 * 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<>();
        List<TreeNode> path = new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root, pre = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                path.add(cur);
                cur = cur.left;
            }
            TreeNode node = stack.peek();
            if (node.right != null && node.right != pre) {
                cur = node.right;
                continue;
            }
            if (node.left == null && node.right == null) {
                StringBuilder sb = new StringBuilder();
                for (TreeNode p : path) {
                    sb.append(p.val).append("->");
                }
                sb.deleteCharAt(sb.length() - 1);
                sb.deleteCharAt(sb.length() - 1);
                res.add(sb.toString());
            }
            pre = stack.pop();
            path.remove(path.size() - 1);
        }
        return res;
    }
}