Maintain an array path[] having node's data on each level , and the length of path[] , on every new level oush the node's data to path[] and increment path len.
If we are at the leaf node , print the path[] , or try recursing to left and right child
#include<stdio.h>
#include<stdlib.h>
struct treeNode
{
int data;
struct treeNode* left;
struct treeNode* right;
};
struct treeNode* newNode(int n)
{
struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
node->data = n;
node->left = NULL;
node->right = NULL;
return node;
}
void printPathsRecur(struct treeNode* node, int pat[], int pathlen);
void printArray(int ints[], int len)
{
int i;
for (i = 0; i<len; i++) {
printf("%d ", ints[i]);
}
printf("\n");
}
void mirror(struct treeNode* node)
{
if (node == NULL)
return;
//go to left node
mirror(node->left);
mirror(node->right);
//swap left and right node child pointers
struct treeNode* temp = node->left;
node->left = node->right;
node -> right = temp;
}
void printPaths(struct node* node)
{
int path[1000];
printPathsRecur(node, path, 0);
}
void printPathsRecur(struct treeNode* node, int pat[], int pathlen)
{
if (node == NULL)
{
return;
}
//add the node to path at this level
pat[pathlen] = node -> data;
//increment path len
++pathlen;
//if its a leaf node , print the path
if (node->right == NULL && node->left == NULL)
{
printArray(pat, pathlen);
}
else
{
//try bith subtree
printPathsRecur(node->left, pat, pathlen);
printPathsRecur(node->right, pat, pathlen);
}
}
int main()
{
struct treeNode *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
/* Print all root-to-leaf paths of the input tree */
printPaths(root);
getchar();
return 0;
}
No comments:
Post a Comment