1 
     1
   /  \
  2    3
 / \   / \
4   5 6   7

对于给定的二叉树，我们需要创建一个矩阵 a[7][7] 满足像 a[2][1]=1 这样的祖先属性，因为 1 是 2 ....

我通过使用额外的空间来解决它一个数组......我想出的解决方案是

int a[n][n]={0};
void updatematrix(int a[][n],struct node *root,int temp[],int index){

if(root == NULL)
  return ;
int i;

for(i=0;i< index;i++)
  a[root->data][temp[i]]=1;
temp[index]=root->data;

updatematrix(a,root->left,temp,index+1);
updatematrix(a,root->right,temp,index+1);
}

我的解决方案有什么错误吗？我们可以就地这样做吗？？？（我的意思是不使用临时数组）

4

1 回答 1

0

temp包含从根到当前节点的路径，即沿着树向下到达当前节点所访问的节点集合。

如果您在每个节点中都有一个父指针（但我猜没有），您可以跟随这些指针并向上遍历树以遍历与temp. 但这会使用更多内存。

您还可以多次沿着树走（伪代码）：

def updatematrix(a,node):
  if node is null: return
  walkDown(a.data,node.left)
  walkDown(a.data,node.right)
  updatematrix(a,node.left)
  updatematrix(a,node.right)

def walkDown(data,node):
  if node is null: return
  a[node][data] = 1
  walkDown(data,node.left)
  walkDown(data,node.right)

相同的复杂性，但内存访问的模式看起来对缓存不太友好。

于 2012-10-01T06:49:59.223 回答