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

This article mainly introduces "how C++ realizes the right pointer of each node". In daily operation, I believe many people have doubts about how C++ realizes the right pointer of each node. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubt of "how C++ realizes the right pointer of each node". Next, please follow the editor to study!

The right pointer of each node

Given a binary tree

Struct Node {

Int val

Node * left

Node * right

Node * next

}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

You may only use constant extra space.

Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1, 2, 3, 4, 5, and 7]

Output: [1,#,2,3,#,4,5,7,#]

Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with "#" signifying the end of each level.

Constraints:

The number of nodes in the given tree is less than 6000.

-100 left) {p = p-> left; break;} if (p-> right) {p = p-> right; break;} p = p-> next;} if (root- > right) root- > right- > next = p If (root- > left) root- > left- > next = root- > right? Root- > right: P; connect (root- > right); connect (root- > left); return root;}}

For non-recursive methods, I was pleasantly surprised to find that the previous method can be used directly without any modification at all. The algorithm can be found in the previous blog Populating Next Right Pointers in Each Node. The code is as follows:

Solution 2:

Class Solution {public: Node* connect (Node* root) {if (! root) return NULL; queue q; q.push (root); while (! q.empty ()) {int len = q.size (); for (int I = 0; I

Next = q.front (); if (t-> left) q.push (t-> left); if (t-> right) q.push (t-> right);}} return root;}}

Although the above two methods can pass OJ, in fact, they do not meet the requirements of the topic. The title says that you can only use constant space, but OJ does not write a test that specifically tests the use of space. Then the constant space solution is affixed below. This solution is also used for sequence traversal, but does not use queue. We build a dummy node to point to the first node of each layer, and then the pointer cur is used to traverse this layer. This is actually traversing one layer, and then connecting the next of the next layer, starting from the root node. If the left child node exists, then the next of the cur is connected to the left child node, and then the cur points to its next pointer. If the right child of the root exists, then the next of the cur is connected to the right child, and then the cur points to its next pointer. At this time, the left and right child nodes of root are connected. At this time, root translates one bit to the right and points to its next pointer. If root does not exist at this time, it means that the current layer has been traversed, reset cur to dummy node, root is now dummy- > next, that is, the first node of the next layer, and then the next pointer of dummy is cleared, or the next pointer of cur can be cleared, because cur has been assigned to dummy previously. So now think about it, why empty it? Because the purpose of using dummy is to point to the location of the first node of the next line, that is, dummy- > next, and once the root is assigned to dummy- > next, the mission of the dummy has been completed and must be disconnected. If it continues to open, then assuming that root is now a leaf node, then the while loop will still execute and will not enter the first two if, and then after the root is empty to the right, it will enter the last if, if dummy- > next has not been broken before. Then root points to the previous leaf node again, and the endless cycle is born and kneels. So be sure to clear it out.

Here again, let's talk about how the dummy node points to the previous node of the first node of each layer. The process is like this. Dummy is a new node created. Its purpose is to point to the first node of the next layer of the root node. Specifically, this is done by relying on the cur pointer. First, cur points to dummy, and then cur connects to the first node of the next layer of root, so the dummy is connected. Then, when the root layer is traversed, the root needs to move down one layer, so that the connection position after the dummy node is assigned to the root, and then the cur points to the dummy,dummy and then disconnects, so it returns to the original state, so that it can all be connected again and again. The code is as follows:

Solution 3:

Class Solution {public: Node* connect (Node* root) {Node* dummy = new Node (- 1), * cur = dummy, * head = root; while (root) {if (root- > left) {cur- > next = root- > left; cur = cur- > next } if (root- > right) {cur- > next = root- > right; cur = cur- > next;} root = root- > next; if (! root) {cur = dummy; root = dummy- > next; dummy- > next = NULL At this point, the study of "how C++ implements the right pointer of each node" is over. I hope I can solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.