Introduction to two methods of finding the image of binary tree by Java programming

Give a binary tree and find its image, as shown in the following figure: the binary tree on the right is the image of the binary tree on the left.

Carefully analyze the characteristics of the two trees to see if you can summarize the steps of seeking the mirror image. The root nodes of the two trees are the same, but their left and right child nodes exchange positions. Therefore, we might as well exchange the two children of the root node in the tree to get the second tree in the following figure

Solution 1 (recursion)

Idea 1: if the current node is empty, return, otherwise exchange the left and right nodes of the node, and recursively exchange the left and right nodes.

The exchange process is as follows:

After exchanging the two children of the root node, we notice that the children of the nodes with values of 10 and 6 remain unchanged, so we also need to exchange the left and right children of the two nodes. The results after the exchange are the third tree and the fourth tree. After these two exchanges, we have traversed all non leaf nodes. At this time, the tree after the exchange happens to be the image of the original tree.

Idea 2: if the current node is null, return null. Otherwise, mirror the left and right children of the node respectively, and then point the left pointer to the right child and the right pointer to the left child to mirror the node.

Solution 2 (non recursive)

Idea 1: traverse the hierarchy. If the root node is not null, join the root node in the queue. If it is judged that the queue is not empty, the node will leave the queue and exchange the left and right children of the node. If the left and right children are not empty, join the left and right children in the queue.

Idea 2: first order traversal. If the root node is not null, put the root node into the stack. When the stack is not null, out of the stack, exchange the left and right nodes. If the left and right nodes are not null, put it into the stack.

summary

The above is all about the two methods of Java programming to find the image of binary tree. I hope it will be helpful to you. Interested friends can continue to refer to this website:

Complete code example of red black tree implemented by Java algorithm

Detailed example of Java Monte Carlo algorithm for approximate value of PI

Java implementation of a variety of sorting algorithm code examples