Leetcode-cn.com/problems/po…

Their thinking

BFS sequence traversal

Let’s join each layer of a binary tree into a linked list from left to right, so it’s a good idea to use BFS to do a sequential traversal of a binary tree directly.

/* // 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; }}; * /
public class Solution {
    public Node connect(Node root) {
        if (root == null) return null;

        Deque<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while(! queue.isEmpty()) {int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node curNode = queue.poll();
                // If it is not the rightmost node of the layer, then it is connected to the first element of the queue (the right node)
                if (i < size - 1) {
                    curNode.next = queue.peek();
                }
                // Since the binary tree is a perfect binary tree, as long as there are left children, there must be right children, no need to determine whether there are right children
                if(curNode.left ! =null) { queue.add(curNode.left); queue.add(curNode.right); }}}returnroot; }}Copy the code

But considering that at the end of the problem, we want to use a constant spatial complexity algorithm, we have the following solution.

recursive

Because the nodes in the current layer can be chained together using the next pointer, you can directly string the nodes in the next layer together.

If there is a left child, it is directly strung together with the right child

Next, determine if the current node is the layer’s rightmost node root.next! = null

If it is not the rightmost node, the child to the right of the current node must also be connected to the node to the right. root.right.next = root.next.left

And then we recursively iterate, and notice here, if it’s the right-most node of this layer, we don’t do anything, because they default the next pointer to null, so we’ve already done that.

public class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        connection(root);
        return root;
    }

    public void connection(Node root) {
        if (root.left == null) return;  // The leaf has been reached
        root.left.next = root.right;
        // If the current node is not the right-most node of the layer, continue to join the nodes together
        Next = null; // Next = null; // Next = null
        if(root.next ! =null) { root.right.next = root.next.left; } connection(root.left); connection(root.right); }}Copy the code