LeetCode117. Populate the next right node pointer for each node_ II

Ideas

116 You can also see the rules by drawing pictures , But this is an upgraded version , Imperfect binary tree . It's easy to think of using hierarchy to traverse , But it's medium , It's definitely not the optimal solution .

Under the analysis of , Hierarchy traversal time complexity O(N), I have achieved the best . Then we can only start from the spatial complexity , The complexity of hierarchical traversal space is O(N), If you don't save a copy , It can be optimized .

When traversing a layer , Just string up the next layer , In this way, the next layer can directly traverse , Don't put it in the queue . The first floor has no upper floor , But the first floor is only root node , There is no need to string them together .

subject

Given a binary tree

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,null,7]
 Output ：[1,#,2,3,#,4,5,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 serialized output is in sequence traversal order （ from  next  Pointer connection ）,'#'  Represents the end of each layer .

Copy

Tips ：

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

Related Topics

• Trees
• Depth-first search
• Breadth first search
• Binary tree
• 441
• 0

Code

    class Solution {

        /**
         *  The head node of the next layer 
         */
        private Node nextRowHead;
        /**
         *  Tail node of the next layer 
         */
        private Node nextRowTail;

        public Node connect(Node root) {
            if (root == null) {
                return root;
            }
            Node curr = root;

            do {
                //  At the end of the inner cycle curr by null, But the first time you come in, you don't need to assign a value , This is the case root
                if (curr == null) {
                    //  Start traversing from the head node of the next line 
                    curr = nextRowHead;
                    nextRowHead = null;
                }

                do {
                    buildNextRow(curr.left);
                    buildNextRow(curr.right);
                    curr = curr.next;
                    //  The next node of the current layer 
                } while (curr != null);
                //  The next layer 
            } while (nextRowHead != null);
            return root;
        }

        /**
         *  Connect the nodes of the next layer 
         */
        private void buildNextRow(Node node) {
            if (node != null) {
                if (nextRowHead == null) {
                    nextRowHead = node;
                    nextRowTail = node;
                } else {
                    nextRowTail.next = node;
                    nextRowTail = node;
                }
            }
        }
    }

Copy

Post Views: 143