用+、-运算符平衡算术表达式树

Question

给定一棵仅由加减法运算符、数字组成的二进制算术表达式树，如何使树尽可能平衡？任务是在不求表达式值的情况下平衡树，即节点数应该保持不变。

示例：

      +                           +
    /   \                      /     \
   +     15      >>>>>>       -       +
 /   \                       / \     / \
5     -                     6   4   5   15
    /   \
   6     4

加法是可交换的和相联的，这允许平衡。交换性允许交换连续“+”节点的子节点。关联性允许旋转。在上述示例中，所执行的转换可以被视为

null

另一种方法可以是将表达式树读入数组，并用变量替换任何'-'子树。然后使用DP确定括号的最佳位置。这必须是自下而上的，这样任何'-'子树在被DP算法考虑时就已经是平衡的了。但是，我很担心，因为可能有(N+1)！排列节点和括号的方法。而我正在寻找一个O(n)算法。

这是一个已知的问题吗？有没有具体的解决方法？

Answer 1

冒着做一些模糊的“评估”（尽管在我看来不是这样）的风险，我会做以下几点：

>

通过将否定标记向下传播到根，将整个树更改为添加节点。一个简单的方法是为每个叶子节点添加一个“颜色”。节点的颜色可以在树的行走过程中直接计算。在遍历过程中，您将跟踪来自-节点的右侧链接的数字（或奇偶校验，因为这是我们唯一感兴趣的部分）；当到达一片叶子时，如果奇偶为偶数，则为绿色，如果奇数为奇数，则为红色。（红叶被否定。）在遍历过程中，-节点更改为+。

      +                          +
    /   \                      /   \
   +    15       >>>>>>       +    15
 /   \                      /   \
5     -                     5    +
    /   \                      /   \
   6     4                    6    -4

现在通过在树叶顶部构造一个最小深度二叉树来最小化树的深度，将树叶按顺序排列，而不考虑前面的树结构：

      +                            +
    /   \                      /       \
   +    15       >>>>>>       +         +
 /   \                      /   \     /   \
5     +                     5    6   -4   15
    /   \
   6    -4

棘手的情况是节点的所有子节点都是红色的。在这种情况下，向上移动树，直到找到一个有绿色后代的父代。您找到的节点必须有两个子节点（否则它的唯一子节点必须有一个绿色的后代节点），其中只有一个子节点有绿色的后代节点。然后，将该节点更改为-，如果右侧子节点有绿色后代，则将其子节点反转，并将右侧子节点（可能是新的）的所有子节点重新着色为绿色。

        +                          +
    /      \                   /       \
   +        +    >>>>>>       +         -
 /   \     /   \            /   \     /   \
5     6   -4   15          5     6   15    4

也许值得指出的是，根节点在左侧有一个绿色的后代，因为第一个叶节点是绿色的。这足以证明上述算法涵盖了所有情况。