I'm trying to find Minimum path sum from root to leaf also need to compute the minimum path. My solution works if the solution is in left sub tree, however if the result is in right subtree root node is added twice in the result path, can someone please take a look at my solution and help me fixing this bug, also suggest better runtime solution if there is any

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();
        }
    }
    
}

I am using backtracking to visit all nodes, I think time complexity of my solution would be O(N) (since all the nodes should be visited, please correct me if am wrong)

CodePudding user response：

Every call of currentpath.add should be mirrored by a call of currentpath.remove. Your code does this fine, except in the bock below:

       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;
            }
        }

So add that call of remove just before return.