LEETCODE -- Populating Next Right Pointers in Each Node

Populating Next Right Pointers in Each Node

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

 

'''

Created on Nov 19, 2014



@author: ScottGu<[email protected], [email protected]>

'''

# Definition for a  binary tree node

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

#         self.next = None



class Solution:

    # @param root, a tree node

    # @return nothing

    def connect(self, root):

        stack=[]

        if(root==None): return

        stack.append(root)

        while(len(stack)!=0):

            for ix in range(len(stack)-1):

                stack[ix].next=stack[ix+1]

            stack[-1].next=None

            cntOfLastLevel=len(stack)

            for ix in range(cntOfLastLevel):

                if (stack[0].left!=None):stack.append(stack[0].left)

                if (stack[0].right!=None):stack.append(stack[0].right)

                stack.remove(stack[0])

        

class Solution2:

    # @param root, a tree node

    # @return nothing

    def connect(self, root):

        if(root==None): return

        head_high=cursor_high=root

        head_low = cursor_low=None

        

        while(cursor_high.left!=None):

            head_low = cursor_low=cursor_high.left

         

            cursor_low.next=cursor_high.right

            cursor_low=cursor_low.next

            while(cursor_high.next!=None):

                cursor_high=cursor_high.next

                cursor_low.next=cursor_high.left

                cursor_low=cursor_low.next

                cursor_low.next=cursor_high.right

                cursor_low=cursor_low.next

            cursor_low.next=None

              

            head_high=cursor_high=head_low

        

제목과 코드는 위에서 말한 바와 같이 이 문제가 비교적 재미있는 점은 이 데이터 구조가 데이터베이스 인덱스 구조와 비슷하다는 것이다. 상술한 코드는 두 가지 방법을 실현했다. 두 가지 방법은 모두 층층이 훑어보고 시간의 복잡도는 모두 O(N)이지만 공간의 복잡도가 다르고 실현의 난이도도 다르다.
1. 첫 번째는 더욱 간단하지만 추가 공간을 사용하여 이전 노드를 저장하는데 사용되며, 최대 공간 복잡도는 모든 잎 노드의 크기를 합친다.그래서 이런 알고리즘이 DB 인덱스를 만드는 데 쓰이면 메모리가 폭발할 것 같고 두 번째 방법은 문제없다.
2. 두 번째는 약간 복잡하지만 공간 복잡도는 O(1)뿐이다. 즉, 추가 메모리가 필요하지 않다.실현 방법은 두 개의 커서와 한 개의 표지 위치를 사용하고, 두 개의 표지는 두 줄의nodes를 병행하여 돌아다니며, 한 개의 표지 위치는 아래의 그 줄의head를 표시하는 데 사용한다.
두 개의 커서가 병행하여 앞으로 가면 동시에 각 자체의 끝까지 간다. 이때 두 개의 커서가 각각 다음 줄로 내려가서 시작하고(이것이 바로 그 줄의 헤드를 표시하는 이유이다) 위의 과정을 반복하여 계속 앞으로 간다. 다음 줄이 없을 때 멈춘다(두 번째 커서는 가리킬 수 없다). 두 개의 커서가 모든nodes를 훑어보고 링크를 추가하는 과정을 스스로 보충해 주십시오.