没有递归的二叉树分支求和

Question

我想在不使用递归的情况下计算二叉树每个分支的总和。我正在尝试使用堆栈，但无法弄清楚如何修复我的代码以获得正确的总和。

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]

Answer 1

Issue with your code is you are not keeping track of the node which has been last popped from your stack.

这是更新后的代码：

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

在上面示例的最后，sums 变量将结果存储为 [11, 10, 18]

Answer 2

我尝试这个是为了好玩，但很惊讶我没有看到任何实际的解决方案。以下是 Kotlin 语言，但可以很容易地转录成 Java。诀窍是在弹出节点之前将状态添加到节点本身以将其标记为已消耗，否则在下一个分支时没有任何值可检查。

这在极少数情况下可能有助于防止堆栈溢出？这在 O(N) 中仍然是运行，但堆栈需要更多 space，并且将访问一个节点两次，一次遍历，一次弹出。

    open class BinaryTree(value: Int) {
    var value = value
    var left: BinaryTree? = null
    var right: BinaryTree? = null
    var consumed: Boolean = false
}

fun branchSums(root: BinaryTree): List<Int> {
    var sumList = ArrayList<Int>()
    var nodeStack = ArrayList<BinaryTree>()
    var valueStack = ArrayList<Int>()

    nodeStack.add(root)

    while(!nodeStack.isEmpty()) {
        val node = nodeStack.get(nodeStack.size-1)

        if (node.consumed) {
            valueStack.removeAt(valueStack.size - 1)
            nodeStack.removeAt(nodeStack.size - 1)
            continue
        }

        valueStack.add(node.value)

        if (node.right == null && node.left == null) {
            var sum = 0
            for (value in valueStack) {
                sum += value
            }
            sumList.add(sum)
        }

        if (node.right != null) {
            nodeStack.add(node.right!!)
        }
        if (node.left != null) {
            nodeStack.add(node.left!!)
        }

        node.consumed = true
    }

    return sumList
}

Answer 3

你可以有这个方法：

 public static int getBranchSum(Node root){
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    int sum=0;
    while (!q.isEmpty()) {            
        Node curNode = q.poll();
        sum+=curNode.data;
        if(curNode.left==null || curNode.right==null)
            curNode.visited=true;
        if(curNode.left != null && curNode.left.visited)
            curNode.visited=true;
        if(curNode.left!=null && !curNode.left.visited)
            q.add(curNode.left);
        else if(curNode.right!=null && !curNode.right.visited)
            q.add(curNode.right);
    }
    root.visited=false;
    return sum;
}

然后在while循环下面调用它，只要输出不等于根数据。

    boolean flag=true;
    List<Integer> list = new ArrayList<>();
    while(flag){
        int result =getBranchSum(root);
        if(result == root.data)
            flag=false;
        else
            list.add(result);
    }
    System.out.println(list);

然而，只有当我们在节点中有一个已访问的布尔值时，以上内容才有效：

class Node{
Node left,right;
int data;
boolean visited = false;
Node(int data){
    this.data=data;
    left=right=null;
}

Answer 4

没有递归的分支求和

def branchSums(root):
    cs=0
    stack=[{"node":root,"cs":cs}]
    sums=[]
    while(len(stack)>0):
        node_info=stack.pop()
        node,cs=node_info["node"],node_info["cs"]
        if node is None:
            continue
        cs=cs+node.value
        if node.left is None and node.right is None:
            sums.append(cs)
            print(sums)
        stack.append({"node":node.right,"cs":cs})
        stack.append({"node":node.left,"cs":cs})

    return sums

没有递归的二叉树分支求和

Binary Tree branch sums without recursion

java

algorithm

binary-tree

data-structures