50220. Ternary Tree Isomorphic

I'm a slow walker, but I never walk backwards.

Task Description

A trenary tree is like a binary tree, and a node has up to three children, left, mid, and right. Please write a function to determine if the two ternary trees are isomorphic. We will define if two two ternary trees are isomorphic recursively.

  • Two empty ternary trees are isomorphic.
  • Two non-empty tenary tress are isomorphic if there is a one-to-one mapping from the children of the first tree to the children of the second tree so that each pair of chilren is isomorphic.

In the following figure the ternary trees tree1 and tree2 are isomorphic. The left subtree of tree1 is isomorphic to the middle subtree of tree2. The middle subtree of tree1 is isomorphic to the right subtree of tree2. The right subtree of tree1 is isomorphic to the left subtree of tree2.

tree1tree1
tree2tree2

The prototype of the function isIsomorphic is in isIsomorphic.h as below.

#include<stdbool.h>
struct TreeNode {
    struct TreeNode *left;
    struct TreeNode *mid;
    struct TreeNode *right;
};
 
typedef struct TreeNode TreeNode;
 
bool isIsomorphic(TreeNode* root1, TreeNode* root2);

You can use the following main.c to test your function.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "isIsomorphic.h"
 
TreeNode *buildTree(TreeNode **roots) {
    int val;
    scanf("%d", &val);
    if(val == 0) return NULL;
 
    TreeNode *now = *roots;
 
    (*roots)++;
 
    now->left = buildTree(roots);
    now->mid = buildTree(roots);
    now->right = buildTree(roots);
 
    return now;
}
 
 
int main() {
    int T, size;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &size);
        TreeNode* root1 = (TreeNode*)calloc(size, sizeof(TreeNode));
        TreeNode* root2 = (TreeNode*)calloc(size, sizeof(TreeNode));
 
        TreeNode *nptr1 = root1, *nptr2 = root2;
 
        root1 = buildTree(&nptr1);
        root2 = buildTree(&nptr2);
 
        isIsomorphic(root1, root2) == true ? printf("True\n") : printf("False\n");
 
        free(root1);
        free(root2);
    }
    return 0;
}

Input Format (for the test main.c)

The first line is the number of test cases T. In the following 3T lines, each three-line is a test case. The first line of each test case is the number of nodes in each tree. The second and third lines are the values of two ternary trees nodes in preorder, where 0's represent NULL pointers. The preorder traversal of a trenary tree consists of the root, followed by the preorder traversal of the left subtree, the middle subtree, and the right subtree. The number of test cases is no more than 20.

Output Format (for the test main.c)

There are T lines, and each line of the output is either "True" or "False" representing if isomorphic or not.

Subtask

  • 40 points: The number of tree nodes is no more than 5.
  • 60 points: The number of tree nodes is no more than 10.

Sample Input

8
8
1 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0
1 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0
1
1 0 0 0
1 0 0 0
2
1 1 0 0 0 0 0
1 0 0 1 0 0 0
4
1 1 0 0 0 1 0 0 0 1 0 0 0
1 1 0 0 0 1 0 0 0 1 0 0 0
3
1 1 0 0 0 1 0 0 0 0
1 1 1 0 0 0 0 0 0 0
3
1 1 0 0 0 1 0 0 0 0
1 0 1 0 1 0 0 0 0 0
3
1 1 0 0 0 0 1 0 0 0
1 1 0 0 0 1 0 0 0 0
8
1 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0
1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0

Sample Output

True
True
True
True
False
False
True
False

Estimated Cyclomatic Number

5

Discussion