我試圖找到從根到葉的最小路徑總和也需要計算最小路徑。如果解決方案在左子樹中，我的解決方案有效，但是如果結果在右子樹中，則在結果路徑中添加兩次根節點，有人可以看看我的解決方案并幫助我修復此錯誤，還建議更好的運行時間如果有解決方案
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)（因為應該訪問所有節點，如果有錯誤請糾正我）
uj5u.com熱心網友回復：
的每次呼叫currentpath.add都應反映在 的呼叫中currentpath.remove。您的代碼可以很好地執行此操作，但以下方框除外：
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;
}
}
remove所以添加之前的呼叫return。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/498087.html
上一篇：在Java中減少二維陣列