遍历来求值，求路径

Binary Tree Paths

• 一道非常好的基础题来区分traversal和DC solution to solve tree related problems

• traversal solution

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root == null) return paths;
        //traversal 想清楚递归3要素
        StringBuilder path = new StringBuilder();
        path.append(root.val);
        dfs(paths, path, root);
        return paths;
    }
    //backtracking 3 factors
    //definition: generate all the paths for tree with root
    private void dfs(List<String> paths, StringBuilder path, TreeNode root) {
        //edge case
        if (root.left == null && root.right == null) {
            paths.add(new String(path));
            return;
        }
        //iteration
        int len = path.length();
        if (root.left != null) {
            path.append("->");
            path.append(root.left.val);
            dfs(paths, path, root.left);
            path.setLength(len);
        }

        if (root.right != null) {
            path.append("->");
            path.append(root.right.val);
            dfs(paths, path, root.right);
            path.setLength(len);
        }
    }
}

DC solution

注意判断root is leaf node的情况

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root == null) return paths;
        //left
        List<String> left = binaryTreePaths(root.left);
        for (String path : left) {
            paths.add(root.val + "->" + path);
        }
        //right
        List<String> right = binaryTreePaths(root.right);
        for (String path : right) {
            paths.add(root.val + "->" + path);
        }
        //root is leaf node
        if (paths.size() == 0) {
            paths.add("" + root.val);
        }
        return paths;
    }
}

Maximum Average Subtree

• D&C

• 为了求double value, 注意除的时候需要cast to double valuef

• int sum = 3, size = 2;

• sum / size = 1, sum / (double) size = 1.5

class Solution {
    double max = 0.00;
    public class Result {
        int size;
        int sum;
        //double average;
        public Result(TreeNode node) {
            size = 1;
            sum = node.val;
        }
    }
    public double maximumAverageSubtree(TreeNode root) {
        //bottom up 
        //d&c 
        Result res = traversal(root);
        return max;
    }

    private Result traversal(TreeNode root) {
        if (root == null) return null;
        Result res = new Result(root);

        Result left = traversal(root.left);
        Result right = traversal(root.right);
        double leftAvg = 0, rightAvg = 0;
        if (left != null) {
            res.size += left.size;
            res.sum += left.sum;
            leftAvg = left.sum /(double) left.size;
        }
        if (right != null) {
            res.size += right.size;
            res.sum += right.sum;
            rightAvg = right.sum / (double) right.size;
        }
        double bigger = Math.max(res.sum / (double) res.size, Math.max(leftAvg, rightAvg));
        max = Math.max(bigger, max);
        return res;
    }
}