Java：二进制树根到叶子路径，最小总和

Question

我试图找到从根到叶的最小路径总和还需要计算最小路径。如果解决方案在左子树中，我的解决方案有效，但是，如果结果在右子树中添加了两次在结果路径中，请有人请看一下我的解决方案并帮助我修复此错误，也建议您更好的运行时间解决方案如果

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import static java.lang.System.out;

public class MinPathSumFromRootToLeaf {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(-1);
        TreeNode left1 = new TreeNode(2);
        TreeNode right1 = new TreeNode(1);//3
        TreeNode left2 = new TreeNode(4);
        root.left = left1;
        root.right = right1;
        left1.left = left2;
        TreeNode left3 = new TreeNode(0);//5
        TreeNode right3 = new TreeNode(1);//6
        right1.left = left3;
        right1.right = right3;
        left3.left = new TreeNode(0);//7
        right3.left = new TreeNode(8);
        right3.right = new TreeNode(1);//9
        printLevelOrder(root);
        shortestPathFromRootToLeaf(root);
    }

    private static void shortestPathFromRootToLeaf(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        int minsum[] = new int[1];
        minsum[0] = Integer.MAX_VALUE;
        backtrack(root, result, new ArrayList<>(), 0, minsum);
        out.println(result + " minsum " + minsum[0]);
    }

    private static void backtrack(TreeNode node, List<Integer> result, List<Integer> currentpath, int currentSum, int[] minsum) {
        if (node == null || currentSum > minsum[0]) {
            return;
        }
        if (node.left == null && node.right == null) {
            if (currentSum + node.val < minsum[0]) {
                minsum[0] = currentSum + node.val;
                currentpath.add(node.val);
                result.clear();
                result.addAll(new ArrayList<>(currentpath));
                return;
            }
        }
        if (node.left != null) {
            currentpath.add(node.val);
            backtrack(node.left, result, currentpath, currentSum + node.val, minsum);
            currentpath.remove(currentpath.size() - 1);
        }
        if (node.right != null) {
            currentpath.add(node.val);
            backtrack(node.right, result, currentpath, currentSum + node.val, minsum);
            currentpath.remove(currentpath.size() - 1);
        }
    }
    
    static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode() {}
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    static class QItem {
        TreeNode node;
        int depth;

        public QItem(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    static void printLevelOrder(TreeNode root) {
        LinkedList<QItem> queue = new LinkedList<>();
        ArrayList<TreeNode> level = new ArrayList<>();
        int depth = height(root);
        queue.add(new QItem(root, depth));
        for (; ; ) {
            QItem curr = queue.poll();
            if (curr.depth < depth) {
                depth = curr.depth;
                for (int i = (int) Math.pow(2, depth) - 1; i > 0; i--) {
                    out.print(" ");
                }
                for (TreeNode n : level) {
                    out.print(n == null ? " " : n.val);
                    for (int i = (int) Math.pow(2, depth + 1); i > 1; i--) {
                        out.print(" ");
                    }
                }
                out.println();
                level.clear();
                if (curr.depth <= 0) {
                    break;
                }
            }
            level.add(curr.node);
            if (curr.node == null) {
                queue.add(new QItem(null, depth - 1));
                queue.add(new QItem(null, depth - 1));
            } else {
                queue.add(new QItem(curr.node.left, depth - 1));
                queue.add(new QItem(curr.node.right, depth - 1));
            }
        }
    }

    static int height(TreeNode root) {
        return root == null ? 0 : 1 + Math.max(
                height(root.left), height(root.right)
        );
    }

    static void printTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode temp = q.poll();
                out.print(" " + temp.val + " ");
                if (temp.left != null) q.offer(temp.left);
                if (temp.right != null) q.offer(temp.right);
            }
            out.println();
        }
    }
    
}

我正在使用回溯来访问所有节点，我认为解决方案的时间复杂性将为o（n）（由于应该访问所有节点，如果错误的话，请纠正我）

Answer 1

currentpath.add的每个呼叫都应通过currentpath.remove的调用来镜像。您的代码可以做到这一点，除了下面的Bock中：

       if (node.left == null && node.right == null) {
            if (currentSum + node.val < minsum[0]) {
                minsum[0] = currentSum + node.val;
                currentpath.add(node.val);
                result.clear();
                result.addAll(new ArrayList<>(currentpath));
                return;
            }
        }

因此，在返回之前添加删除的呼叫。