https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree


Success.

___

```python
class Solution:
    def get_nodes_separated_by_levels(self, root):
        if root == None:
            return []
        
        a_list = [root]
        b_list = []
        switch_flag = 0
        level_list = []

        while True:
            if len(a_list) == 0 and len(b_list) == 0:
                break
            
            if switch_flag == 0:
                for node in a_list:
                    if node.left:
                        b_list.append(node.left)
                    if node.right:
                        b_list.append(node.right)
                level_list.append([n for n in a_list])
                a_list = []
                switch_flag = 1
            else:
                for node in b_list:
                    if node.left:
                        a_list.append(node.left)
                    if node.right:
                        a_list.append(node.right)
                level_list.append([n for n in b_list])
                b_list = []
                switch_flag = 0
        
        return level_list

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        #2023/01/10 08:48, copied from last solution
        self.answer = None
        self.node_list = []

        def travel(node):
            if self.answer != None:
                return

            if node:
                self.node_list.append(node)
                
                value_list = [node.val]
                if node.left != None:
                    value_list.append(node.left.val)
                if node.right != None:
                    value_list.append(node.right.val)
                #print(value_list)
                if p.val in value_list and q.val in value_list:
                    self.answer = node
                    return

                travel(node.left)
                travel(node.right)
        travel(root)

        def check_the_node(node):
            value_list = []
            
            def travel_x(node_):
                if node_:
                    value_list.append(node_.val)
                    if node_.left:
                        travel_x(node_.left)
                    if node_.right:
                        travel_x(node_.right)
            travel_x(node)

            if p.val in value_list and q.val in value_list:
                self.answer = node
        
        if self.answer != None:
            return self.answer
        else:
            self.node_list = []
            for sub_list in self.get_nodes_separated_by_levels(root):
                self.node_list += sub_list
            for node in self.node_list:
                #print(node.val)
                check_the_node(node)
            if self.answer == None:
                return root
            else:
                return self.answer
        #2023/01/10 08:49
```
