Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "how C++ expands the binary tree into a linked list". The editor shows you the operation process through an actual case, and the operation method is simple, fast and practical. I hope this article "how C++ expands the binary tree into a linked list" can help you solve the problem.

Expand the binary tree into a linked list

Given a binary tree, flatten it to a linked list in-place.

For example

Given

one

/

2 5

/

3 4 6

The flattened tree should look like:

one

two

three

four

five

six

Click to show hints.

Hints:

If you notice carefully in the flattened tree, each node "s right child points to the next node of a pre-order trave

This problem requires the binary tree to be expanded into a linked list, and according to the order of the linked list formed after the expansion, it is analyzed that the preorder traversal is used, so as long as it is a number traversal, there are recursive and non-recursive methods to solve it. Here we also use two methods to solve the problem. First of all, let's look at the recursive version, the idea is to first use DFS's idea to find the most left child node, then go back to its parent node, disconnect the parent node from the right child node, connect the original left child node to the right child node of the parent node, and then connect the original right child node to the right child node of the new right child node, and then go back to the previous parent node to do the same operation. The code is as follows:

Solution 1:

Class Solution {public: void flatten (TreeNode * root) {if (! root) return; if (root- > left) flatten (root- > left); if (root- > right) flatten (root- > right); TreeNode * tmp = root- > right; root- > right = root- > left; root- > left = NULL; while (root- > right) root = root- > right; root- > right = tmp;}

For example, for the following binary tree, the transformation process of the above algorithm is as follows:

1 / 2 5 / 3 4 6 1 / 2 5 3 6 4 1 2 3 4 5 6

Next, let's look at the implementation of the non-iterative version. this method starts from the root node, first detects the existence of its left child node, and if so, disconnects the root node from its right child node. Connect the left child node and all the structures behind it to the position of the original right child node, and connect the original right child node to the last right child node of the element left child node. The code is as follows:

Solution 2:

Class Solution {public: void flatten (TreeNode * root) {TreeNode * cur = root; while (cur) {if (cur- > left) {TreeNode * p = cur- > left; while (p-> right) p = p-> right; p-> right = cur- > right; cur- > right = cur- > left; cur- > left = NULL } cur = cur- > right;}

For example, for the following binary tree, the transformation process of the above algorithm is as follows:

1 / 2 5 / 3 4 6 1 2 / 3 4 5 6 1 2 3 4 5 6

The iterative solution of the preorder is as follows:

Solution 3:

Class Solution {public: void flatten (TreeNode* root) {if (! root) return; stack s; s.push (root); while (! s.empty ()) {TreeNode* t = s.top (); s.pop (); if (t-> left) {TreeNode* r = t-> left; while (r-> right) r = r-> right R-> right = t-> right; t-> right = t-> left; t-> left = NULL;} if (t-> right) s.push (t-> right);}}. That's all for "how C++ expands the binary tree into a linked list". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

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.