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

与えられた二分木に対して、1は2の祖先であるため、a [2] [1]=1のような祖先プロパティを満たす行列a[7][7]を作成する必要があります...。

私は余分なスペースと配列を使用してそれを解決しました...私が思いついた解決策は

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 に答える