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

This article mainly introduces the relevant knowledge of "how C++ solves the right pointer problem of each node". The editor shows you the operation process through an actual case, and the operation method is simple, fast and practical. I hope that this "C++ how to solve the right pointer problem of each node" article can help you solve the problem.

The right pointer of each node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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.

Example:

Input: {"$id": "1", "left": {"$id": "2", "left": "$id": "3", "left": null, "next": null, "right": null, "val": 4}, "next": null, "right": {"$id": "4", "left": null, "next": null, "right": null, "val": 5}, "val": 2}, "next": null, "right": {"$id": "5" Left: {"$id": "6", "left": null, "next": null, "right": null, "val": 6}, "next": null, "right": {"$id": "7", "left": null, "next": null, "right": null, "val": 7}, "val": 3}, "val": 1}

Output: {"$id": "1", "left": {"$id": "2", "left": {"$id": "3", "left": null, "next": {"$id": "4", "left": null, "next": {"$id": "5", "left": null, "next": {"$id": "6", "left": null, "next": null, "right": null, "val": 7}, "right": null Val: 6}, right: null, val: 5}, right: null, val: 4}, next: {"$id": "7", "left": {"$ref": "5"}, "next": null, "right": {"$ref": "6"}, "val": 3}, "right": {"$ref": "4"}, "val": 2}, "next": null, "right": {"$ref": "7"} "val": 1}

Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

Note:

You may only use constant extra space.

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

This question is actually the application of tree sequence traversal, you can refer to the previous blog Binary Tree Level Order Traversal, since it is traversal, there are recursive and non-recursive methods, it is best to master both methods, to be able to write. Let's first take a look at the recursive solution. Since it is a complete binary tree, if the left child node of a node exists, its right child node must exist, so the next pointer of the left child node can directly point to its right child node. The processing method for its right child node is to determine whether the next of its parent node is null. If not, it points to the left child node of the node to which its next pointer points. If it is null, it points to NULL. The code is as follows:

Solution 1:

Class Solution {public: Node* connect (Node* root) {if (! root) return NULL; if (root- > left) root- > left- > next = root- > right; if (root- > right) root- > right- > next = root- > next? Root- > next- > left: NULL; connect (root- > left); connect (root- > right); return root;}}

The non-recursive solution is a little more complicated, but it is not particularly complicated, and it needs to be assisted by queue. Because it is a sequential traversal, the nodes of each layer are added to the queue sequentially, and every time an element is taken out from the queue, the next pointer is pointed to the next node in the queue. Before the beginning elements of each layer start traversing, count the total number of the layer and use a for loop. So that when the for loop ends, the layer has been traversed, as shown in the following code:

Solution 2:

/ / Non-recursion, more than constant spaceclass Solution {public: Node* connect (Node* root) {if (! root) return NULL; queue q; q.push (root); while (! q.empty ()) {int size = 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;}}

Let's take a look at the following awesome method, using two pointers, start and cur, in which start marks the start node of each layer, and cur is used to traverse the nodes of that layer.

Solution 3:

/ Non-recursion, constant spaceclass Solution {public: Node* connect (Node* root) {if (! root) return NULL; Node* start = root, * cur = NULL; while (start- > left) {cur = start; while (cur) {cur- > left- > next = cur- > right; if (cur- > next) cur- > right- > next = cur- > next- > left Cur = cur- > next;} start = start- > left;} return root;}}; that's all for "how C++ solves the right pointer problem of each node". 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.