How to realize the isomorphism of trees with Java
This article mainly introduces how to use Java to achieve tree isomorphism, the article introduces in great detail, has a certain reference value, interested friends must read it!
Given two trees R1 and R2, if R1 can be interchanged several times between the left subtree and the right subtree to make them exactly the same as R2, it means that they are isomorphic.
Give an example
The construction of trees
Trees can be constructed from arrays or linked lists: for example, the tree in the upper-left corner of the image above can be represented by an array as
0123456789101112ABCDEGMurray Fmuri H-
This method wastes some space, but it is suitable to represent a complete binary tree.
The linked list mode is more intuitive.
In addition to the above two ways, we can also use the way of "class array".
Public static class Node {String data;int left;int right;}
For example: the tree in the upper left corner of the image above can be represented as
Array index dataleftright0A121B342C6-3D--4E5-5F--6G7-7Hmuri-
The tree structure of this article uses the third way.
Terminal input:
A class TongGou {private Scanner scanner;public TongGou () {scanner = new Scanner (System.in);} / / tree structure public static class Node {String data;int left;int right;} / * create a tree * @ param nodes* @ return*/public int createTree (Node [] nodes) {int N = nodes.length;int root =-1Interint [] check = new int [N] Arrays.fill (check,0); / / initialize to 0for (int item0) {check [left] = 1;} if (right > 0) {check [right] = 1;} for (int item0)
