Daily classic

Five of the Thirteen Songs in the South Garden — Li He (Tang)

Why don’t you take wu hook, charge guan Shan fifty states.

Please you temporarily on the Lingyan Pavilion, if a scholar wanhuhou?

describe

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow-up:

  • You may only use constant extra space.
  • The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root =,2,3,4,5,6,7 [1] the Output: [1 #, 2, 3, and #, 4, 7, #] Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.Copy the code

Example 2:

Input: root = []
Output: []
Copy the code

Note:

The number of nodes in the tree is in the range [0, 2^12 - 1].
-1000 <= Node.val <= 1000
Copy the code

parsing

Given a perfect binary tree, in which all leaves are on the same level, each parent node has two child nodes, the structure definition of each node is also given, and the next pointer of each node points to the right node of its same level. If there is no next right node, the next pointer is set to NULL. Initially, all next Pointers are set to NULL. The title also puts higher demands on elite athletes:

  • You can only use extra space at a constant level
  • Use a recursive approach

At first glance, I don’t know how to start with this problem, but it is also easy to solve by knowing the rules clearly. First of all, I think as long as it is a tree problem, basically 99% can be solved by DFS, and this problem is no exception. There are three key points to this question:

  • The first is how to determine that the rightmost node next is None. In fact, we can see from the example that as long as its parent node next is None, its next is None.
  • The second key point is where the next of the right child points to the left node of the node when there is a node to its right.
  • The third problem is when the recursion stops, that is, when the node is empty or there is no node at the next level, it is easy to judge that there is no node at the next level, just judge that the left of a node is empty.

To solve these three key problems, define a DFS function that assigns values to the next of the left and right children of the current node when the root node is the current node.

answer

class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        self.dfs(root)
        return root
        
    def dfs(self, root):
        if not root or not root.left: return 
        root.left.next = root.right
        if root.next:
            root.right.next = root.next.left
        else:
            root.right.next = None
        self.dfs(root.left)
        self.dfs(root.right)
            
        
        
        	      
		
Copy the code

The results

Runtime: In the linked submissions online, MPG for Each Node is given in Each Node. Memory Usage: For Each Node in the Python online submission for Populating Next Right Pointers.Copy the code

parsing

From the feature that the next of the nodes in the problem points from left to right, we can think of solving the problem with the idea of BFS. Start with the root node and place each node in the stack. Next to the left and right nodes, use stack.pop() and stack.pop(0). Assignment of next to each node is not affected.

answer

class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        stack = [root]
        while stack:
            node = stack.pop()
            if node and node.left:
                node.left.next = node.right
                if node.next:
                    node.right.next = node.next.left
                else:
                    node.right.next = None
                stack.append(node.left)
                stack.append(node.right)
        return root
                
        
        
                
        
        
Copy the code

The results

Runtime: 13 ms, faster than 77.19% in the given Python online submission for Populating Next Right Pointers in Each Node. Submissions in the Python online submissions for Populating the Next Right Pointers in Each Node.Copy the code

Original link: leetcode.com/problems/po…

Your support is my biggest motivation