b_wy_最优路径（构造树+dfs）

import java.util.*;
import java.math.*;
import java.io.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(final int x) { val = x; }
}
class Solution {
    int n;
    String A[];
    int order=0;
    TreeNode build(int i) {
        if (i>=n) return null;
        TreeNode root;
        if (A[i].equals("null")) {
            return null;
        }
        root = new TreeNode(Integer.parseInt(A[i]));
        root.left = build(i+1);
        root.right = build(i+2);
        return root;
    }
    LinkedList<Integer> path;
    List<List<Integer> > all;
    void dfs(TreeNode root, int tar) {
        if (root == null)
            return;
        path.add(root.val);
        if (tar == root.val) {
            List<Integer> t = new LinkedList<>(path);
            t.add(order++);
            all.add(t);
        }
        //System.out.println(tar);
        dfs(root.left, tar-root.val);
        dfs(root.right, tar-root.val);
        path.removeLast();
    }
    void init() throws IOException {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        String s = sc.next();
        A = s.substring(1,s.length()-1).split(",");
       // System.out.println(s.substring(1,s.length()-1));
        int tar = sc.nextInt();
        n = A.length;
        TreeNode root = build(0);
        all = new LinkedList<>();
        path = new LinkedList<>();
        dfs(root, tar);
        
        if (all.isEmpty()) {
            System.out.println("[]");
        } else {
            List<String> ss = new ArrayList<>();
            for (List<Integer> p : all) {
                StringBuilder sb = new StringBuilder();
                for (int x : p) sb.append(x);
                ss.add(sb.toString());
            }
            String[] sA = (String[])ss.toArray();

            Arrays.sort(sA, new Comparator<String>() {
	        @Override
	        public int compare(String a, String b) {
		    if (a.length() == b.length()) {
                        return a.charAt(a.length()-1)-b.charAt(b.length()-1);
                }
                return a.length() - b.length();
            });
            String t = sA[0];
            t.substring(1, t.length()-1);
            t = String.join(",", t);
            System.out.println("[" + t + "]");
        }
    }
}
public class Main{
    public static void main(String[] args) throws IOException {  
        Solution s = new Solution();
        s.init();
    }
}

b_wy_最优路径（构造树+dfs）

原文：https://www.cnblogs.com/wdt1/p/14586303.html