博客

不难，考察代码编写能力

116. Populating Next Right Pointers in Each Node

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if not root:
            return None 
        def isP(n):
            for i in range(1,n+1):
                if 2**i-1==n:
                    return True 
                elif 2**i>n:
                    return False
            return False
        def isQ(n):
            for i in range(1,n):
                if 2**i==n:
                    return True 
                elif 2**i>n:
                    return False
            return False
        stack=[root]
        count=0
        pre=TreeLinkNode(0)
        while stack:
            now = stack.pop(0)
            count+=1
            if isQ(count):
                pre=now 
            else:
                pre.next=now
                pre=pre.next
            if now.left:
                stack.append(now.left)
                stack.append(now.right)

117. Populating Next Right Pointers in Each Node II

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if not root:
            return None 
    
        stack=[root]
        
        while stack:
            mystack=[]
            pre=None
            while stack:
                curr=stack.pop()
                if pre:
                    pre.next=curr 
                pre=curr
                mystack.append(curr)
            while mystack:
                node = mystack.pop()
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)