How to implement a golang program that flips a binary tree

Flip Binary Tree golang

Binary tree flipping is a classic algorithm question and is often asked in interviews. In this article, we will implement a golang program that flips a binary tree.

What is a binary tree

A binary tree is a tree structure that consists of a limited set of nodes, including a root node, and each node is connected to the left and right child respectively. node. When all nodes have no left or right child nodes, the tree structure is called a binary tree.

In golang, structures are often used to represent binary tree nodes. For example:

type TreeNode struct {

Val int
Left *TreeNode
Right *TreeNode

}

We use the above code to define a binary tree node, where Val represents the value of the node, Left represents the left child node, and Right Represents the right child node.

How to flip a binary tree

The problem of flipping a binary tree seems simple, but it actually involves some complex issues. For the convenience of explanation, we assume that there is a binary tree as follows:

4
/ \
2 7

 / \
6   9

After flipping, the binary tree should become:

 4

/ \
7 2
/ \
9 6

In terms of code implementation, we can use recursive methods to solve this problem. The recursive method can directly use the pointer of the structure to exchange the positions of the left and right child nodes. The code of the recursive method is as follows:

func invertTree(root TreeNode) TreeNode {

if root == nil {
    return nil
}

root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root

}

We declare a function named invertTree, This function receives a pointer to the root node of a binary tree as a parameter and returns a pointer to a new flipped binary tree. If the root node is empty, nil is returned.

Inside the function body, we use recursion to complete the process of flipping the binary tree. We exchange the left child node and the right child node of the root node, and then apply this process recursively to the child nodes.

Finally, we return the root node pointer of the flipped new binary tree.

The complete code is as follows:

package main

import "fmt"

type TreeNode struct {

Val int
Left *TreeNode
Right *TreeNode

}

func invertTree(root TreeNode) TreeNode {

if root == nil {
    return nil
}

root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root

}

func main() {

root := &TreeNode{Val: 4, Left: &TreeNode{Val: 2},
    Right: &TreeNode{Val: 7, Left: &TreeNode{Val: 6}, 
           Right: &TreeNode{Val: 9}}}

fmt.Println("Before invert: ")
fmt.Println(root.Val, root.Left.Val, root.Right.Val, root.Right.Left.Val, root.Right.Right.Val)

invertTree(root)

fmt.Println("After invert: ")
fmt.Println(root.Val, root.Left.Val, root.Right.Val, root.Left.Left.Val, root.Left.Right.Val)

}

at In this example, we first define the root node of a binary tree. In the main function, we call the invertTree function to flip the binary tree. Finally, we print out the binary tree before and after flipping.

Conclusion

In this article, we showed a golang program on how to flip a binary tree. By using a simple recursive function, our program can solve this problem very well. I hope this article will help everyone understand the problem of binary tree flipping and the use of golang language.

The above is the detailed content of How to implement a golang program that flips a binary tree. For more information, please follow other related articles on the PHP Chinese website!