Binary Tree Paths

题目:

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

分析:

15分钟,无bug,注意

res.add( convertToString(path) );
// res.add( new String ( convertToString(path) ) );
// 两个都可以,就是说函数返回值本身就放在一个新的instance里面

解法:

public class Solution {
    /**
     * @param root the root of the binary tree
     * @return all root-to-leaf paths
     */
    public String convertToString(List<TreeNode> path) {
        String res = "";
        for (int i = 0; i < path.size() - 1; i++) {
            res = res + Integer.toString(path.get(i).val) + "->";
        }
        int last = path.get(path.size() - 1).val;
        res += Integer.toString(last);
        return res;
    } 

    public void dfs(List<String> res, List<TreeNode> path, TreeNode root) {
        if (root.left == null && root.right == null) {
            res.add( convertToString(path) );
            // res.add( new String ( convertToString(path) ) );
            // 两个都可以,就是说函数返回值本身就放在一个新的instance里面
            return;
        }
        if (root.left != null) {
            path.add(root.left);
            dfs(res, path, root.left);
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            path.add(root.right);
            dfs(res, path, root.right);
            path.remove(path.size() - 1);
        }
    }

    public List<String> binaryTreePaths(TreeNode root) {
        // Write your code here
        List<String> res = new ArrayList<String>();
        if (root == null) {
            return res;
        }
        List<TreeNode> path = new ArrayList<TreeNode>();
        path.add(root);
        dfs(res, path, root);
        return res;
    }
}

results matching ""

    No results matching ""