“This is the 21st day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge 2021”.

Populates the next right-side node pointer for each node

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

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
Copy the code

Populate 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.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/po… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: sequence traversal
  • First, if root is empty or both the left and right child nodes are empty, the next pointer is not handled and root is returned directly.
  • Otherwise, when the binary tree has more than one node, the sequential traversal of the binary tree is used to record the nodes of each layer of the binary tree, and then the next pointer of each node of the current layer is processed in sequence. Since the order of all nodes has not changed during processing, root is returned.
import com.kaesar.leetcode.Node;

import java.util.LinkedList;
import java.util.Queue;

public class LeetCode_116 {
    public static Node connect(Node root) {
        // If root is empty or both the left and right nodes are empty, no action is required
        if (root == null) {
            return root;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        // Use queues to record nodes at each level
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(root);
        while(! nodes.isEmpty()) {int count = nodes.size();
            Node last = nodes.poll();
            if(last.left ! =null) {
                nodes.add(last.left);
            }
            if(last.right ! =null) {
                nodes.add(last.right);
            }

            count--;
// Process the next pointer for each layer of nodes
            while (count > 0) {
                Node curNode = nodes.poll();
                if(curNode.left ! =null) {
                    nodes.add(curNode.left);
                }
                if(curNode.right ! =null) { nodes.add(curNode.right); } last.next = curNode; last = curNode; count--; }}return root;
    }

    public static void main(String[] args) {
        // Test case
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        // Before processing
        root.print();
        connect(root);
        System.out.println();
        // After processingroot.print(); }}Copy the code

【 Daily message 】 Good good study, day day up.