algorithm - 为二叉树创建祖先矩阵

Question

     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);
}

我的解决方案有什么错误吗？我们可以就地执行此操作吗？？？(我的意思是不使用临时数组)

Answer 1

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)

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