java - 二叉树分支求和而不递归

我试图不使用递归来计算二叉树的每个分支的总和。我正在尝试使用堆栈，却无法弄清楚如何修正我的代码以获取正确的总和。

public static List<Integer> branchSums(BinaryTree root) {
    LinkedList<BinaryTree> toVisit = new LinkedList<>();
    BinaryTree current = root;
    List<Integer> sums = new ArrayList<>();
    int sum = 0;

    while (current != null || !toVisit.isEmpty()) {
        while (current != null) {
            sum += current.value;
            toVisit.push(current);
            current = current.left;
        }

        current = toVisit.pop();

        // if found leaf add sum to results and decrement sum by current node
        if (current.left == null && current.right == null) {
            sums.add(sum);
            sum -= current.value;
        }

        current = current.right;
    }

return sums;
}

输入示例：

         1
      /      \
     2        3
   /   \    /   \
  4     5  6     7
 / \   /
8   9 10

输出示例[15、16、18、10、11]

最佳答案

您的代码存在问题是您没有跟踪哪个节点
  从堆栈中最后弹出。


这是更新的代码：

public static List<Integer> caculateSum(BinaryTree root) {
    List<Integer> sums = new ArrayList<>();
    int sum=0;
    BinaryTree current = root, popped=null;
    Stack<BinaryTree> s = new Stack<BinaryTree>();
    while(current!=null ) {
        //checking if last node popped from stack is not equal to left or right node of current node
        if(popped==null||((current.left!=null && !current.left.equals(popped)) && (current.right!=null && !current.right.equals(popped)))) {
            while(current != null) {
                sum+=current.value;
                s.push(current);
                current = current.left;

            }
        }
        current=s.peek();
        if(current.right == null) {
            //if current node is leaf node
            if(current.left == null) {
                sums.add(sum);
            }
            sum-=current.value;
            popped = current;
            s.pop();
        } else if(current.right!=null && current.right.equals(popped)){
            //if current node both left and right nodes have been processed
            sum-=current.value;
            popped = current;
            s.pop();
        }else {
            //if current node right part is not processed
            sum+=current.right.value;
            s.push(current.right);
        }
        if(s.isEmpty()) {
            break;
        }
        current=s.peek();
    }
    return sums;
}

将通过一个例子对此进行解释。假设我们给出了二叉树

1,2,9,3,7，null，8,5

在上面的代码中，除了旧变量之外，还使用了新变量popped来跟踪从堆栈中弹出的最后一个元素。

因此，以下是主要步骤：


首先从current节点开始，我们要检查当前剩余节点是否不等于弹出窗口（如果相等，则意味着已经处理了current节点剩余部分，因此我们无需再次对其进行处理）。同样，我们正在检查current节点的右节点是否不等于popped节点（如果相等，则意味着我们已经处理过current节点的右节点，这间接意味着也处理了left节点）。
现在，对于栈顶节点current，我们检查：


如果其right节点为null如果为true，则表示current
node是叶节点，或者是其right的已处理节点
node为空（例如在我们的示例节点中，值为3）。如果是
叶，我们将其添加到我们的sums列表中。此外，对于这两种情况，我们都将其删除
此top节点并从当前sum值中减去其值
（这件事也已经在上面的代码中完成了。）
将在popped变量中跟踪堆栈中弹出的元素。
如果其权限不为null，但其right节点等于popped
节点在处理过的while循环的最后一遍时发生
此right节点。这意味着对于堆栈的顶部节点，左侧和左侧
正确的节点已被处理，因此我们弹出该节点并保持
在popped变量中跟踪它。
否则，我们将栈顶元素的右节点推入栈中。



在以上示例的末尾，sums变量会将结果存储为[11，10，18]

关于java - 二叉树分支求和而不递归，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/60349451/