[Python] BFS and Euler Path - with picture
The Euler path is a useful tool to have for solving any LCA problem here is how it works:\n1. Find the deepest nodes using BFS\n2. Traverse the graph visiting r
The Euler path is a useful tool to have for solving any LCA problem here is how it works:\n1. Find the deepest nodes using BFS\n2. Traverse the graph visiting **root, left, root, right, root** to make a Euler Path\n3. Return the node (LCA) that is at the lowest depth between **p** and **q** in the Euler Path\n\n<img src="https://assets.leetcode.com/users/images/062b2e0e-65a1-4203-a51d-18fff04f8b2c_1604555931.5770352.png" width="50%">\n\n**In this problem, p and q would be the two of the deepest nodes in the tree 7 and 4\nand the lowest depth node between them is node 2 ~ which is the LCA of 7 and 4**\n\n<br>\n\n```python\ndef subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n\t\n\tdef get_deepest_nodes(root):\n\t\tq = [root]\n\t\twhile q:\n\t\t\tnext_level = []\n\t\t\tfor node in q:\n\t\t\t\tif node.left:\n\t\t\t\t\tnext_level.append(node.left)\n\t\t\t\tif node.right:\n\t\t\t\t\tnext_level.append(node.right)\n\n\t\t\tif next_level:\n\t\t\t\tq = next_level\n\t\t\telse:\n\t\t\t\tbreak\n\t\treturn q\n\n\tdef euler_path(node, d):\n\t\tnonlocal depth, path\n\n\t\tpath.append(node)\n\t\tdepth.append(d)\n\n\t\tif node.left:\n\t\t\teuler_path(node.left, d+1)\n\t\t\tpath.append(node)\n\t\t\tdepth.append(d)\n\n\t\tif node.right:\n\t\t\teuler_path(node.right, d+1)\n\t\t\tpath.append(node)\n\t\t\tdepth.append(d)\n\n\tif not root.left and not root.right: return root\n\t\n\t# Make an Euler path\n\tpath = []\n\tdepth = []\n\teuler_path(root, 0)\n\t\n\t# Find the deepest nodes\n\tdeepest_nodes = get_deepest_nodes(root)\n\t\n\t# Find the LCA of the deepest nodes\n\ti = min(path.index(node) for node in deepest_nodes)\n\tj = max(path.index(node) for node in deepest_nodes)\n\treturn path[min(range(i, j+1), key = lambda k: depth[k])]\n```
[]