Python Solution - Recursive Elegant Solution
I thought that this solution was a little different to the others posted, most of them doing a level order search using the next pointer. However here, I have r
I thought that this solution was a little different to the others posted, most of them doing a level order search using the next pointer. However here, I have recursively split the tree into \'pincer\' segments (this is what I call them because I don\'t know the name), at each level the pair is made up of 1. the right most node of that level in the left node\'s subtree & 2. the left most node of that level in the right node\'s subtree - and then connected node 1 to node 2 at each level.\n\n```\nclass Solution:\n    def connect(self, root: \'Optional[Node]\') -> \'Optional[Node]\':\n        if not root:\n            return\n        \n        c1, c2 = root.left, root.right\n        \n        while c1 and c2:\n            c1.next = c2\n            c1, c2 = c1.right, c2.left\n        \n        self.connect(root.left)\n        self.connect(root.right)\n        \n        return root\n```\n\t\nThe idea being, that I could simply connect a node\'s left child to it\'s right child, with the only difficulty being to find the \'next\' node of a right child. The \'pincer\' segments help resolve this issue, as the \'next\' node of a right child is simply the other node in that level of the \'pincer\'\n\nI\'m not quite sure the if there is a specific name for this general idea, and would be very appreciative if anyone knows what it is Hope this helps!\n\nEDIT: A diagram illustrating the \'pincer segments\' of each of the first three nodes, and the pointers created by each - in red, blue and green respectively. Note that each node not on the left or right \'boundary\' is visited by two other \'pincer segments\', as is necessary since each node should have a pointer coming in and one coming out.\n\n![image](https://assets.leetcode.com/users/images/3e380898-de6f-4ab5-89e6-8a618ff56199_1640908417.4581368.jpeg)
['Depth-First Search', 'Recursion', 'Python']