为二叉树创建祖先矩阵 [英] create ancestor matrix for binary tree

问题描述

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

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

for the given binary tree we need to create a matrix a[7][7] satisfying the ancestor property like a[2][1]=1 since 1 is an ancestor of 2 ....

我通过使用额外的数组来解决它...解决方案i

i solved it by using extra space an array ...the solution i came up is

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

我的解决方案是否有错误？
可以代替吗？（我的意思是不使用temp数组）

is there any mistake in my solution ? can we do this inplace ???(i mean without using the temp array )

推荐答案

temp 包含从根到当前节点的路径，即在沿着树走到当前节点时访问的节点集。

temp contains the path from root to current node, i.e. the set of nodes visited while walking down the tree to arrive at the current node.

如果每个节点中都有一个父指针（但我想不是），则可以跟随这些指针并沿着树走，以与 temp 遍历相同的节点集。但这会占用更多内存。

If you have a parent pointer in each node (but I guess not), you can follow those pointers and walk up the tree to traverse the same set of nodes as temp. But this uses more memory.

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

You can also walk down the tree several times (pseudocode):

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)

相同的复杂度，但是内存访问模式看起来对缓存的友好度较低。

Same complexity, but the pattern of memory access looks less cache friendly.

这篇关于为二叉树创建祖先矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！