Untitled

mail@pastecode.io avatar
unknown
python
a year ago
1.3 kB
1
Indexable
Never
from collections import iter:

class Node:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None


    def get_root():
        values = iter([3, 8, 6, 9, None, None, 11, 10, None, None,
                       12, None, None, 7, None, None, 4, 5, None, None, 13, None, None])

        def tree_recur(itr):
            val = next(itr)
            if val is not None:
                node = Node(val)
                node.left = tree_recur(itr)
                node.right = tree_recur(itr)
                return node

        return tree_recur(values)

    def dfids():
        root = get_root()
        res = float("inf")

        def dfids_search(node, depth, limit):
            if depth <= limit and node is not None:
                val = node.val
                if val == 12:
                    nonlocal res
                    res = min(res, depth)
                else:
                    dfids_search(node.left, depth + 1, limit)
                    dfids_search(node.right, depth + 1, limit)

        for limit in range(1, 5):
            dfids_search(root, 0, limit)
            if res < float("inf"):
                return res
        return -1