Article From:https://www.cnblogs.com/liuliu5151/p/9124367.html

Given a binary tree

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

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.

Note:

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

Example:

Given the following binary tree,

     1
   /  \
  2    3
 / \    \
4   5    7

After calling your function, the tree should look like:

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \    \
4-> 5 -> 7 -> NULL

 

The meaning of the question is:

Given an arbitrary two binary tree, each node has next pointer.

Try to point the next pointer to the adjacent node on the right side of the same layer.

 

Ideas:

Recursion, the solution is very clever.

Using 1 as curr, connect curr.left:2 and curr.right:3 with pre. Because the next of root node 1 points to null and leaves the for loop.
            1  ( curr )--->null 
            /  \
dummy(-1):pre--> 2---> 3
           / \    \
          4   5    7




Connect (dummy.next) is called recursively because dummy.next points.2here2 For curr. Use pre to connect curr.left:4 and curr.right:5.
                   1  
               /        \
                   2(curr)---> 3
             / \            \
dummy(-1):pre--> 4--->5 7

Continue with the for cycle, curr = curr.next, when curr is 3. Continue using pre to connect curr.left (3 left child tree to Null) and curr.right:7.

      1
             /    \
                   2 ---> 3(curr)
         / \ \
dummy(-1):pre--> 4--->5 --->7

Because at this point, curr's next points to null and exits the for loop.
Continue to invoke connect (dummy.next) recursively until root = = null, return

Code:

 1 public class Solution {
 2     public void connect(TreeLinkNode root) {
 3         if (root == null) return;
 4 
 5         TreeLinkNode dummy = new TreeLinkNode(-1);
 6         for (TreeLinkNode curr = root, prev = dummy;
 7                 curr != null; curr = curr.next) {
 8             if (curr.left != null){
 9                 prev.next = curr.left;
10                 prev = prev.next;
11             }
12             if (curr.right != null){
13                 prev.next = curr.right;
14                 prev = prev.next;
15             }
16         }
17         connect(dummy.next);
18     }
19 }

 

 

Similar Posts:

Leave a Reply

Your email address will not be published. Required fields are marked *