“This is the 12th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Topic describes

Given a perfect binary tree, all leaf nodes are at the same level and each parent node has two children. Binary trees are defined as follows:

struct Node { int val; Node *left; Node *right; Node *next; } populates each of its next Pointers to point to its next right-hand node. If the next right-side node cannot be found, set the next pointer to NULL.

Initially, all next Pointers are set to NULL.

  • Example 1:

Enter: root = [1,2,3,4,5,6,7]

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

Explanation: Given A binary tree as shown in Figure A, your function should populate each of its next Pointers to point to its next node on the right, as shown in Figure B. The serialized outputs are traversed in order, with nodes of the same layer connected by the next pointer, ‘#’ marking the end of each layer. Source: LeetCode

  • Advanced:
  1. You can only use constant level extra space.
  2. Using recursion is also acceptable, in this case the stack space occupied by the recursive program does not count as additional space complexity.

Subject analysis

After studying this problem for a long time, I did not understand what the topic meant. Finally, I understood the algorithm was really bald, but it was quite interesting to brush it.

The following is the main idea of this question:

  1. Because each node contains the index of left node left and right node right, the connection can be completed by directly pointing the next of left node left to right, so that 2 and 3, 4 and 5, 6 and 7 can be connected in pairs.
  2. How should we connect nodes that are not the same child node, such as child node 5 and child node, we can connect nodes by right of node 2 and left of node 3;
  3. Recurse the above steps until the child node is null to stop traversal.

Time complexity: O(n), where n is the number of nodes in the binary tree.

Space complexity: O(m), where M is the height of the binary tree.

/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; }}; */ class Solution { public Node connect(Node root) { if(root == null) return null; // Get the left and right child nodes of the root Node. Node right = root.right; ConnectTwoNode (left,right); return root; } // Define a recursive function, Given two nodes connected to them public void connectTwoNode (Node node1, Node 2) {/ / appear blank nodes returned directly if (node1 = = null | | 2 = = null) {return; } // Associate the current two nodes (e.g. 2/3) node1.next = node2; // Connect nodes of the same parent node (e.g. 4/5, 6/7) connectTwoNode(node1.left,node1.right); connectTwoNode(node2.left,node2.right); // Connect different children of the parent node (e.g. 5, 6) connectTwoNode(node1.right,node2.left); }}Copy the code

The official website also provides a solution with less space complexity, which is directly posted here for you to study:

class Solution { public Node connect(Node root) { if (root == null) { return root; } // Start from the root Node. while (leftmost.left ! = null) {// Update next pointer Node head = leftmost; while (head ! = null) { // CONNECTION 1 head.left.next = head.right; // CONNECTION 2 if (head.next ! = null) { head.right.next = head.next.left; } // Move the pointer back head = head.next; } // Go to the next level leftmost node leftmost = leftmost. } return root; }}Copy the code