Java | Beauty and Easy solution! | Explained & Visualized | O(n) algo, O(1) memo |
The task boils down to understanding the structure of the tree and how to traverse it.\nThe solution is that we create a method that contains the right and left
The task boils down to understanding the structure of the tree and how to traverse it.\nThe solution is that we create a method that **contains the right and left nodes of the same level**.\n1. We connect the left node with the right one using the `next` field.\n2. The **next** left node of the current left one is combined with the **next** right one.\n3. The **next** left node of the current right node is combined with the **next** right node.\n4. And we also take **the next right node of the left one** and combine it with **the left node of the right one**. This is the most difficult step and is the key to solving the problem.\n\n**See the image below!** It turns out that we first connected two nodes and then connected their next level. Moreover, first they combined the "children" of the left, then the "children" of the right, and then they were united.\n\n```java\nclass Solution {\n        public static Node connect(Node root) {\n        if (root == null || (root.left == null && root.right == null)) return root;\n\n        connectNext(root.left, root.right);\n\n        return root;\n    }\n\n    private static void connectNext(Node left, Node right) {\n        if (left == null || right == null) return;\n        left.next = right; // Step 1 - comments only for the image below!\n\t\t\n        connectNext(left.left, left.right); // Step 2\n        connectNext(left.right, right.left); // Step 3\n        connectNext(right.left, right.right); // Step 4\n    }\n}\n```\n![image](https://assets.leetcode.com/users/images/1f554560-3085-44a7-b2e8-b16c0958a069_1666979901.3168855.png)\n\n
['Depth-First Search', 'Breadth-First Search', 'Recursion', 'Java']