[트리] Populating Next Right Pointers in Each Node

2796 단어
제목:
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.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

  •  
    For example,Given the following perfect binary tree,
             1
           /  \
          2    3
         / \  / \
        4  5  6  7
    

     
    After calling your function, the tree should look like:
             1 -> NULL
           /  \
          2 -> 3 -> NULL
         / \  / \
        4->5->6->7 -> NULL

    생각:
    층차가 두 갈래 트리를 두루 돌아다니며 각 층의 이전 노드의next를 다음 노드를 가리키고 대기열을 사용하여 층차를 보조할 때 대기열에서 NULL로 각 층의 노드를 분할합니다.
    /**
     * Definition for binary tree with next pointer.
     * function TreeLinkNode(val) {
     *     this.val = val;
     *     this.left = this.right = this.next = null;
     * }
     */
    
    /**
     * @param {TreeLinkNode} root
     * @return {void} Do not return anything, modify tree in-place instead.
     */
    var connect = function(root) {
        if(root==null){
            return;
        }
        
        var stack=[],pre=null;
        stack.push(root);
        stack.push(null);
        
        while(stack.length!=0){
            var p=stack.unshift();
            
            if(p!=null){
                if(p.left){
                    stack.push(p.left);
                }
                if(p.right){
                    stack.push(p.right);
                }
            }else{
                if(stack.length!=0){
                    stack.push(null);
                }
            } 
            
            
            if(pre!=null){
                pre.next=p;
            }
            
            pre=p;
        }
    };

    좋은 웹페이지 즐겨찾기