Leetcode: Populating Next Right Pointer in Each Node

1623 단어
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
    
    상수 저장 공간을 요구하기 때문에 층으로 훑어볼 수 없다
    /**
     * Definition for binary tree with next pointer.
     * public class TreeLinkNode {
     *     int val;
     *     TreeLinkNode left, right, next;
     *     TreeLinkNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public void connect(TreeLinkNode root) {
    		// Start typing your Java solution below
    		// DO NOT write main() function
    		while(root != null){
    			TreeLinkNode pre = root;
    			TreeLinkNode sib;
    			while(pre != null){
    				if(pre.left != null)
    					pre.left.next = pre.right;
    				sib = pre.next;
    				if(sib != null && pre.right != null)
    					pre.right.next = sib.left;
    				pre = sib;
    			}
    			root = root.left;
    		}
    	}
    }

    좋은 웹페이지 즐겨찾기