Shulou(Shulou.com)06/01 Report--

Mirror binary tree example analysis, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

The algorithm is very difficult, and even if you understand the logic, it is still not easy to write it in code. There are too many details to deal with inside. In order to make it easy for everyone to understand the algorithm logic, for all the topics, I will use the form of picture and text plus animation to explain, so that readers can easily understand the algorithm logic, but also can leave a profound image not easy to forget.

OK, let's start today's algorithm: mirrored binary tree is to swap all the left and right nodes of a binary tree, just like the binary tree in the mirror, the left and right direction is in the opposite direction.

Binary tree node representation

Class Node {

T value

Node left

Node right

Node (T value) {

This.value = value

}

Node (T value, Node left, Node right) {

This.value = value

This.left = left

This.right = right

}

}

The constructor of one parameter is the leaf node, and the constructor of the three parameters is the intermediate node. When you see here, the reader should know that this is the Java language. I used the paradigm.

Construct binary tree

Node node2 = new Node (2)

Node node3 = new Node (3)

Node node1 = new Node (1, node2, node3)

/ / one-time construction

Node node1 = new Node (1, new Node (2), new Node (3))

Present a binary tree structure

If we write the mirroring algorithm correctly, how can we visually verify that the structure of the mirror is correct? LeetCode uses unit tests, which use a series of unit test and stress test script code to verify the correctness and performance of algorithms written by users. But let's not do this because it's not intuitive. We choose to visually present the structure and content of the binary tree, so that we can use the naked eye for quick verification. How to present it intuitively? We use the simplest parenthesis representation, which is not the most intuitive, but it is easy to implement.

Class Node {

T value

Node left

Node right

Public String toString () {

/ / Leaf node

If (left = = right) {

Return String.format ("[% d]", value)

}

/ / intermediate node

Return String.format ("(d, s, s)", value, left, right)

}

}

Node node2 = new Node (2)

Node node3 = new Node (3)

Node node1 = new Node (1, node2, node3)

System.out.println (node1)

System.out.println (node2)

System.out.println (node3)

-

[2]

[3]

(1, [2], [3])

Recursive mirror binary tree

There are two algorithms for mirrored binary trees, one is recursion and the other is iteration. The recursive algorithm is simple and easy to understand, so we first use the recursive algorithm to solve the problem. The idea of recursion is to traverse deeply, encounter a node, first recursively mirror its left subtree, then recursively mirror its right subtree, and then exchange its own left and right subtrees. If you encounter a leaf node, you don't have to deal with it. In order to avoid infinite recursion, the stop condition of recursion must be set in time, where the stop condition is to encounter the leaf node.

Public void mirrorFrom (Node node) {

/ / Leaf node

If (node.left = = node.right) {

Return

}

/ / Recursively mirror the left subtree

If (node.left! = null)

MirrorFrom (node.left)

/ / Recursive mirror right subtree

If (node.right! = null)

MirrorFrom (node.right)

/ / swap the left and right subtrees of the current node

Node tmp = node.left

Node.left = node.right

Node.right = tmp

}

Iterative mirror binary tree

The advantage of recursive algorithm is that the logic is simple, but the disadvantage is that every time a recursive function is called, a new function stack is added. If the tree is too deep, the stack memory of the function will continue to rise, accidentally triggering the infamous exception StackOverflowException. If the binary tree is evenly distributed, then the tree will not be too deep, but if you encounter a biased binary tree, for example, if all the child nodes are hung on the right node, the binary tree will degenerate into a linear linked list, and the length of the linked list is the depth of the tree. then the depth of this tree is scary.

So let me introduce the second algorithm-iterative algorithm. The basic idea of iteration is to convert the recursive algorithm into a loop algorithm and use a for loop to exchange the left and right subtrees of all nodes. We need to re-understand the goal of the algorithm, which is very simple, which is to traverse the whole binary tree and swap the left and right pointers of all the intermediate nodes encountered during the traversal.

So how to design this cycle? One obvious approach is a hierarchical loop, where the first loop deals with the layer 1 binary tree node, which is the only root node. The next loop deals with the layer 2 binary tree node, the two sons of the root node. This is done all the way to the bottom, and the condition for the termination of the loop is that the descendant node is gone. So we need to use a container to hold the descendant nodes that need to be processed in the next loop.

Public MirrorBinaryTree mirrorByLoop () {

/ / empty trees do not need to be processed

If (root = = null) {

Return this

}

/ / nodes to be processed in the current loop

LinkedList expandings = new LinkedList ()

Expandings.add (root)

/ / the loop can be terminated without a background node

While (! expandings.isEmpty ()) {

/ / Node to be processed in the next loop

/ / that is, all the son nodes of the current node

LinkedList nextExpandings = new LinkedList ()

/ / traversing all nodes in the current layer

For (Node node: expandings) {

/ / collect the descendant nodes and save them for the next cycle

If (node.left! = null) {

NextExpandings.add (node.left)

}

If (node.right! = null) {

NextExpandings.add (node.right)

}

/ / swap the left and right pointers of the current node

Node tmp = node.left

Node.left = node.right

Node.right = tmp

}

/ / set the descendant node as the target node of the next cycle

Expandings = nextExpandings

}

Return this

}

Complete code

The following complete code can be copied and run directly. If the reader is still not clear enough, you are welcome to ask questions in the message area.

Package leetcode

Import java.util.LinkedList

Public class MirrorBinaryTree {

Static class Node {

T value

Node left

Node right

Node (T value) {

This.value = value

}

Node (T value, Node left, Node right) {

This (value)

This.left = left

This.right = right

}

Public String toString () {

If (left = = right) {

Return String.format ("[% d]", value)

}

Return String.format ("(d, s, s)", value, left, right)

}

}

Private Node root

Public MirrorBinaryTree (Node root) {

This.root = root

}

Public MirrorBinaryTree mirrorByLoop () {

If (root = = null) {

Return this

}

LinkedList expandings = new LinkedList ()

Expandings.add (root)

While (! expandings.isEmpty ()) {

LinkedList nextExpandings = new LinkedList ()

For (Node node: expandings) {

If (node.left! = null) {

NextExpandings.add (node.left)

}

If (node.right! = null) {

NextExpandings.add (node.right)

}

Node tmp = node.left

Node.left = node.right

Node.right = tmp

}

Expandings = nextExpandings

}

Return this

}

Public MirrorBinaryTree mirrorByRecursive () {

MirrorFrom (root)

Return this

}

Public void mirrorFrom (Node node) {

If (node.left = = node.right) {

Return

}

If (node.left! = null)

MirrorFrom (node.left)

If (node.right! = null)

MirrorFrom (node.right)

Node tmp = node.left

Node.left = node.right

Node.right = tmp

}

Public String toString () {

If (root = = null) {

Return "()"

}

Return root.toString ()

}

Public static void main (String [] args) {

Node root = new Node (

one,

New Node (

two,

New Node (4)

New Node (

five,

New Node (8)

Null))

New Node (

three,

New Node (

six,

Null

New Node (9))

New Node (7))

MirrorBinaryTree tree = new MirrorBinaryTree (root)

System.out.println (tree)

Tree.mirrorByRecursive ()

System.out.println (tree)

Tree.mirrorByLoop ()

System.out.println (tree)

}

}

-

(1, (2, [4], (5, [8], null)), (3, (6, null, [9]), [7]))

(1, (3, [7], (6, [9], null)), (2, (5, null, [8]), [4]))

(1, (2, [4], (5, [8], null)), (3, (6, null, [9]), [7]))

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.