3.9题意为已知二叉树的前序遍历结果和中序遍历结果，要求重建二叉树。之所以在这里说3.9，是因为解第八题的时候为了处理输入建成二叉树，实现了一个重建二叉树的函数。
代码如下（六个参数分别为前序遍历结果数组，其起点和终点；中序遍历结果数组，其起点和终点）：
node* buildTree(int* nodesPre,int s1,int e1,int* nodesIn,int s2,int e2) { if (s1 > e1) { return NULL; } if (s2 > e2) { return NULL; } node* root = new node; root->data = nodesPre[s1]; int lenOfLeft = 0; for (;s2 + lenOfLeft <= e2;lenOfLeft++) { if (nodesPre[s1] == nodesIn[s2 + lenOfLeft]) break; } root->left = buildTree(nodesPre,s1+1,s1+lenOfLeft,nodesIn,s2,s2+lenOfLeft-1); root->right = buildTree(nodesPre,s1+lenOfLeft+1,e1,nodesIn,s2+lenOfLeft+1,e2); return root; }
回到3.8，遍历树中的所有节点，为每个节点生成由0和1组成的串作为ID，递归定义，节点a的左孩子ID为ID(a).push_back(1)，右孩子ID为ID(a).push_back(0)。即根的ID为空串，在遍历过程中，每向左走一次，就在其父节点ID后添加一个1作为其ID，若向右则添加一个0。如图中的节点8，ID为111，即因为它可以通过从根节点连续三次向左走来到达。
有了这个ID，就可以很容易地计算两个节点之间的距离了。先给出递归遍历所有节点并计算ID的函数：
void buildMap(node* root,map
一个点的ID表示了从根节点需要经过怎样的路径能到达它。于是，若两个点的ID开头有相同的部分，说明它们在一开始路径是一直的，即没有分离，这段路径不会增加两者的距离。忽略掉开头的相同部分后，两者ID中剩下的部分就代表了两者完全不同的路径了，将两者ID剩余部分的长度相加即得到了两者的距离。如图中的节点8和节点5，ID分别是111和10，忽略掉开头的一个1后，两者的剩余部分分别是11和0，则distance(8,5)=length(11)+length(0)=2+1=3。
计算两个节点距离的函数如下：
int findDistance(map
最新评论