leetcode------Populating Next Right Pointers in Each Node II

6966 단어 LeetCode
제목:
Populating Next Right Pointers in Each Node II
통과율:
31.7%
난이도:
어렵다
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
  • You may only use constant extra space.

  •  
    For 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


    , 。
     1 /**
    
     2  * Definition for binary tree with next pointer.
    
     3  * public class TreeLinkNode {
    
     4  *     int val;
    
     5  *     TreeLinkNode left, right, next;
    
     6  *     TreeLinkNode(int x) { val = x; }
    
     7  * }
    
     8  */
    
     9 public class Solution {
    
    10     public void connect(TreeLinkNode root) {
    
    11         int count=1,tmp=0;
    
    12         LinkedList<TreeLinkNode> queue=new LinkedList<TreeLinkNode>();
    
    13         TreeLinkNode start=null,sec=null,pre=null;
    
    14         if(root!=null){
    
    15          queue.addLast(root);
    
    16         }
    
    17         while(!queue.isEmpty()){
    
    18             pre=queue.pollFirst();
    
    19                 if(count==1)pre.next=null;
    
    20                 if(pre.left!=null){
    
    21                     queue.addLast(pre.left);
    
    22                     tmp++;
    
    23                 }
    
    24                 if(pre.right!=null){
    
    25                     queue.addLast(pre.right);
    
    26                     tmp++;
    
    27                 }
    
    28 
    
    29             for(int i=1;i<count;i++){
    
    30                 start=queue.pollFirst();
    
    31                 pre.next=start;
    
    32                 pre=start;
    
    33                 if(start.left!=null){
    
    34                     queue.addLast(start.left);
    
    35                     tmp++;
    
    36                 }
    
    37                 if(start.right!=null){
    
    38                     queue.addLast(start.right);
    
    39                     tmp++;
    
    40                 }
    
    41             }
    
    42             count=tmp;
    
    43             tmp=0;
    
    44             if(start!=null)
    
    45             start.next=null;
    
    46         }
    
    47         
    
    48     }
    
    49 }

    좋은 웹페이지 즐겨찾기