这是业务上遇到的一个真实问题。不过原问题比较抽象，为了便于表述，转成一个大家熟悉的场景。
问题描述
某小国的行政划分包含国，省，市，区四个级别。它们的关系在逻辑上满足树结构，即:
- 除了国以外的节点，有且仅有一个父节点。例如某区只可能属于唯一的市
- 每个节点有0~N个子节点。例如省可以有多个市， 区没有下属行政单位
该小国的法律规定，低级的行政区域继承它的上属行政区域的法律条文，并可根据实际情况自治。
每个行政区域的政府数据库里记录了增量的部分。
---文件名: countryA/rule
#国A
rules = {
'increase': ['A1', 'A2', 'A3']
}
---文件名:countryA/provinceA/rule
#省A
rules = {
'increase': ['A4'],
'decrease': ['A1']
}
上面的例子表示国A的条文是A1, A2, A3， 省A的条文是A2, A3, A4，因为省A首先继承了国A的条文。
不仅如此，每个行政区域的记录还可以加入简单的条件判断（条文受外部事件影响，例如当发生战争时，新增某个条文），记录方式如下:
if condition:
rules = {'increase': ['A1', 'A2']}
else:
rules = {'increase': ['A1', 'A3']}
有一天发生了事故，黑客入侵了系统，删除了数据库里的记录。
幸运的是有一个备份系统存储了所有行政区域在不同外部条件下的具体条文。
例如某区C的快照如下:
- no_condition:
A1, A2, A3, A4, A5 - condition1:
A1, A2, A4, A5 - condition2:
A1, A2, A4, A6 - condition3:
A1, A2, A5, A6
现在，希望你写个程序把被删掉的记录(每个行政区域的增量记录)恢复。
问题分析
这个问题有两个关键点:
- 把每个节点的全量数据转成以增量数据
- 反推条件对值的作用
根据题意，这是一个树形结构，我们首先把数据结构定义好。
public class Node {
private String name; //节点名称
private Node father; //父节点
private List<Node> sonList; //子节点列表
private List<String> rules; //节点的rules
private List<String> increaseRules; //节点增加的rules
private List<String> decreaseRules; //节点减少的rules
}
public class Tree {
private String name; //树名称
private Node rootNode; //树的根节点
}
定义好数据结构后，整理输入和输出。
输入:
假设有5个condition，输入为5份文件，每份文件记录了一堆节点信息（只有节点名称和rules)， 示例如下：
# condition1
[
{
'name': 'countryA/provinceC/cityM/rules',
'rules': ['A1', 'A2', 'A3']
},
{...}
]
输出：
1 份文件， 文件记录每个节点的增量信息和条件表达式。示例:
if condition1:
node1_increase_rules = ['A1']
else:
node1_increase_rules = ['A2']
node1_decrease_rules = []
node1 = {
'name': 'countryA/provinceC/cityM/rules',
'increase_rules': node1_increase_rules,
'decrease_rules': node1_decrease_rules
}
node_list = [node1, ...]
接下来，就是把结构建好，并转化成我们最终想要的结果了。我们分两步解决：
- 在默认的
condition（参考系）下, 把节点组织成树，并补全节点的信息。 - 依次代入一个
condition，比较相同位置的节点之间的差异。
第一步的关键是组织这棵树，可以采用深度优先的方式，从根节点开始，把子节点加入sonList中，树就组好了。通过对比父子节点的rules成员变量，可以把子节点的increaseRules和decreaseRules计算出来。
第二步的关键是找到不同树中相同位置（其实就是name相同）的节点，并对比节点的值如何受到condition影响。要注意的是，对比两节点的时候，要比较的是increaseRules和decreaseRules，而不是rules， 因为我们的配置记录的是increaseRules和decreaseRules
问题解决
实际工程中"法律条文"这一块是字典形式，编码实现起来比较冗长，就不贴代码了。针对上面的问题，大致把类和函数定义下，其实只要思路清晰，代码还是很好写的。
---
public class Node {
private String name; //节点名称
private Node father; //父节点
private List<Node> sonList; //子节点列表
private List<String> rules; //节点的rules
private List<String> increaseRules; //节点增加的rules
private List<String> decreaseRules; //节点减少的rules
}
public class Tree {
private String name; //树名称
private Node rootNode; //树的根节点
}
---
public interface Tool {
// condition 编码
String conditionEncode(Map<String, String> condition);
// condition解码
Map conditionDecode(String conditionId);
}
---
public interface NodeInterface {
// 生成Node节点，根据父节点的rules和子节点的rules补全Node的信息
Node generateNode(Node father, String name, List<String> fatherRules, List<String> currentRules);
// 比较两个节点，返回increaseRules 和 decreaseRules
Map<String, List> compareTwoNodes(Node origin, Node current);
}
---
public interface TreeInterface {
// 根据节点列表构建一棵树
Tree buildTree(List<Node> nodeList, String treeName);
// 从树中根据节点名称找到节点
Node getNodeFromTreeByNodeName(Tree tree, String nodeName);
}
总结
这个问题刚开始拿到的时候觉得非常困难，主要是数据结构和工程中的各种细节特例混杂在一起，思路不清晰。当尝试着把数据结构剥离出来后，其实并不困难。在平时的编码工作中，对每一个功能点，要优先确立数据结构，建立正确的模型。
