LeetCode116. Populate the next right node pointer for each node

This paper is finally updated at 484 Days ago, , The information may have developed or changed .

One 、 Ideas

after drawing Find out , The connection between sons is OK . But the grandchildren of different fathers have problems connecting , It's OK to solve one , The trick is to recurse , Can solve all these problems . Always thinking about solving problems Divide and conquer , But after the partition, I didn't expect to restore it ...

Two 、 problem

Given a   Perfect binary tree  , All its leaf nodes are on the same layer , Each parent node has two children . A binary tree is defined as follows ：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Copy

Fill in each of its next The pointer , Let this pointer point to its next right node . If the next right node cannot be found , Will next The pointer is set to NULL.

In the initial state , all  next The pointer is set to NULL.

Advanced ：

• You can only use constant level extra space .
• Using recursion to solve problems also meets the requirements , In this problem, the stack space occupied by recursive program is not considered as additional space complexity .

Example ：

 Input ：root = [1,2,3,4,5,6,7]
 Output ：[1,#,2,3,#,4,5,6,7,#]
 explain ： A given binary tree is shown in figure  A  Shown , Your function should fill in every one of its  next  The pointer , To point to its next right node , Pictured  B  Shown . The output of the serialization is arranged in sequence traversal , Nodes on the same layer are controlled by  next  Pointer connection ,'#'  It marks the end of every layer .

Copy

Tips ：

• The number of nodes in the tree is less than  4096
• -1000 <= node.val <= 1000

Related Topics

• Trees
• Depth-first search
• Breadth first search

\n

• 404
• 0

3、 ... and 、 Code

public Node connect(Node root) {
            if (root == null) {
                return null;
            }
            convert(root.left, root.right);
            return root;
        }

        private void convert(Node left, Node right) {
            if (left == null || right == null) {
                return;
            }
            left.next = right;
            convert(left.left, left.right);
            convert(right.left, right.right);
            convert(left.right, right.left);
        }

Copy

Post Views: 297