Recursively, python solution AC


  • 0
    class Solution(object):
    def searchnext(self,node,currnode):
        if node.left==currnode and node.right!=None:
            return node.right
        else:
            while node.next:
                node=node.next
                if node.left!=None and node.left!=currnode:return node.left
                if node.right!=None and node.right!=currnode:return node.right
            return None
    def searchstart(self,node):
        if not node.left and not node.right:return None
        if node.left:return node.left
        return self.searchnext(node,node.left)
    def connect(self, root):
        """
        :type root: TreeLinkNode
        :rtype: nothing
        """
        # for perfect binary tree
        '''if not root:return
        while root.left:
            p=root
            while p!=None:
                p.left.next=p.right
                if p.next:
                    p.right.next=p.next.left
                p=p.next
            root=root.left'''
        #solution: if it is not so perfet,but TLE
        while root:
            start=self.searchstart(root)
            currnode=start
            nextnode=self.searchnext(root,start)
            while nextnode:
                currnode.next=nextnode
                currnode=nextnode
                nextnode=self.searchnext(root,currnode)
            root=start
    

    For solution 2,I want to solve the problem that the tree is not so perfect, the idea is come from http://www.cnblogs.com/felixfang/p/3647898.html,but TLE. so if someone have another idea for sharing or pls tell me what's wrong wirh my solution,THx!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.