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

This article mainly shows you "how to realize the flipping tree algorithm in big data". The content is simple and clear. I hope it can help you solve your doubts. Next, let the editor lead you to study and learn the article "how to realize the flipping tree algorithm in big data".

Algorithm:

Personally, I think the root of this type of problem lies in the understanding of the topic, so it is important to understand the definition of flipped binary tree.

Let's first take a look at what a flip binary tree is: flipping means that the root node remains the same, and the left and right subtrees change places, of course, the left and right subtrees here must also be the flipped binary tree.

Solution:

1. The binary trees of empty nodes and single nodes do not need to be flipped. 2.1) binary trees with more than two nodes, first flip their left and right subtrees, 2) then exchange positions with the left and right subtrees of the root node.

Topic 1:

Https://leetcode-cn.com/problems/invert-binary-tree/

Code implementation:

/ * Definition for a binary tree node. * type TreeNode struct {* Val int * Left * TreeNode * Right * TreeNode *} * / func invertTree (root * TreeNode) * TreeNode {/ / 1. The root node is nil and directly returns if root = = nil {return root} / / 2. The left and right nodes flip the rotor tree first, and then flip the child l: = invertTree (root.Left) r: = invertTree (root.Right) root.Left,root.Right = r return root l return root}

Execution result:

Topic 2:

Solution:

Is the transformation of topic 1: the binary tree part flips we observe that the flipped binary tree will find that the level of the flipped nodes does not change, but the left and right positions are swapped. For this reason, we split this topic into. 1. The left and right subtrees of both trees are the same. two。 The left subtree of the two trees = = right subtree, and the right subtree = = left subtree. 3. If both trees are nil, they are the same. 4. If one of the two trees is nil, it is different. 5. If the root node values of the two trees are different, the whole tree is different.

Https://leetcode-cn.com/problems/flip-equivalent-binary-trees/

Code implementation:

/ * Definition for a binary tree node. * type TreeNode struct {* Val int * Left * TreeNode * Right * TreeNode *} * / func flipEquiv (root1 * TreeNode, root2 * TreeNode) bool {/ / 1. If both root1,root2 are nil, if root1 = = root2 {return true} / / 2. Root1 One of root2 is nil, or the other is not nil or root1 is different from root2 if root1 = = nil | | root2 = = nil | | root1.Val! = root2.Val {return false} / / 3. Root1,root2 is the same, further check their children Nothing more than the following two return (flipEquiv (root1.Left,root2.Left) & & flipEquiv (root1.Right,root2.Right)) | | (flipEquiv (root1.Right,root2.Left) & & flipEquiv (root1.Left,root2.Right))}

Execution result:

These are all the contents of the article "how to realize the flipping tree algorithm in big data". Thank you for your reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

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.