Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example: Given the below binary tree and sum = 22,

注意题目是从root到leaf有没有这个path存在

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        if(root.val == sum){
            if(root.left == null && root.right == null) return true;
        } 
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

Path Sum II lc 113

列出所有的solution

很明显用dfs，但是这里我

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/**
 * 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<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root == null) return result;
        List<Integer> list = new ArrayList<Integer>();

        helper(result, list, root, sum);
        return result;
    }
    public void helper(List<List<Integer>> result,List<Integer> list,TreeNode root, int sum ){

        list.add(root.val);
        if(root.left == null && root.right == null){
            if(sum ==  root.val){
                result.add(new ArrayList<Integer>(list));
                //list.remove(list.size() - 1);
            }
            return;
        }


        if(root.left != null){
            helper(result, list,root.left, sum - root.val);
            list.remove(list.size() - 1);
        }
        if(root.right != null){
            helper(result, list,root.right, sum - root.val); 
             list.remove(list.size() - 1);

        }

        //list.remove(list.size() - 1);
    }
}

Path Sum III(437)

Find the number of paths that sum to a given value.The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

public class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root == null)
            return 0;
        return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }

    public int findPath(TreeNode root, int sum){
        int res = 0;
        if(root == null)
            return res;
        if(sum == root.val)
            res++;
        res += findPath(root.left, sum - root.val);
        res += findPath(root.right, sum - root.val);
        return res;
    }

}

面经题 minpath root to leaf min path

import java.util.ArrayList;
import java.util.List;

public class NaryTreePathCost {
 private static int minCost = Integer.MAX_VALUE;
    public List<Integer> findMinCostFromRootToLeaf(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        List<Integer> curr = new ArrayList<>();
        findMinCostHelper(root, root.val, curr, result);

        return result;
    }


    private void findMinCostHelper(TreeNode root, int cost, List<Integer> 
                                   curr, List<Integer> result) {
        curr.add(root.val);
        if (root.children == null || root.children.length == 0) {
            if (cost < minCost) {
                minCost = cost;
                result.clear();
                result.addAll(new ArrayList<>(curr));
            }
            return;
        }

        for (TreeNode child : root.children) {

            findMinCostHelper(child, cost + child.val, curr, result);
            curr.remove(curr.size() - 1);
        }
    }


    public static void main(String[] args) {
     NaryTreePathCost sol = new NaryTreePathCost();

        TreeNode root = new TreeNode(1, 2);
        root.children[0] = new TreeNode(2, 2);
        root.children[1] = new TreeNode(3, 3);
        root.children[0].children[0] = new TreeNode(4, 0);
        root.children[0].children[1] = new TreeNode(2, 0);
        root.children[1].children[0] = new TreeNode(3, 0);
        root.children[1].children[1] = new TreeNode(2, 0);
        root.children[1].children[2] = new TreeNode(0, 0);

        List<Integer> result = sol.findMinCostFromRootToLeaf(root);

        for (Integer e : result) {
            System.out.print(e + " ");
        }

        System.out.println("");
        System.out.println(minCost);
    }

    static class TreeNode {
        int val;
        TreeNode[] children;

        public TreeNode(int val, int n) {
            this.val = val;
            this.children = new TreeNode[n];
        }
    }
}