257. Binary Tree Paths

Borris 的个人博客 / 0 / 0 / 创建于 5年前 / 更新于 5年前

解法一 Recursive (String or StringBuilder)

思路

使用 preorder traversal, 我们可以通过 String 的叠加或者 StringBuilder 的 append(), 对路径进行遍历。
我们需要定义一个 ArrayList 返回所有路径；使用 StringBuilder 使需要新建 SB 对象。
定义一个遍历树的方法 searchTree：
如果这个节点本身为 null, 那么就退出遍历；如果某个节点左右子都为 null, 就将所记录的字符串添加进 ArrayList 中；否则，对这个节点的左右子树进行 searchTree() 的递归调用。

代码

// 使用 String 叠加
Class Solution () {
    public List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> paths = new ArrayList<>();
        searchTree(root, "", paths);
        return paths;
    }
    public void searchTree (TreeNode root, String str, ArrayList<String> paths) {
        if (root == null) {
            return;
        }
        // 至少说明 root 在路径中因为非 null
        if (root.left == null && root.right == null) {
            paths.add(str + root.val);
        }
        // 其他情况，说明 root 在路径中， str 要添加 root.val，再搜索左右子树是否有路径
        searchTree(root.left, str + root.val + "->", paths);
        searchTree(root.right, str + root.val + "->", paths);
    }
}

// 使用 StringBuilder
Class Solution () {
    public List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> paths = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        searchTree(root, sb, paths);
        return paths;
    }
    public void searchTree (TreeNode root, StringBuilder sb, ArrayList<String> paths) {
        if (root == null) {
            return;
        }
        // 至少说明 root 在路径中因为非 null
        int len = sb.length();
        sb.append(root.val);
        if (root.left == null && root.right == null) {
            paths.add(sb.toString());
        }
        // 其他情况，说明 root 在路径中
        sb.append("->");
        searchTree(root.left, sb, paths);
        searchTree(root.right, sb, paths);
        sb.setLength(len); // back track to before root
    }
}