<reponame>Linchin/python_leetcode_git
"""
863
all nodes distance k in binary tree
medium

We are given a binary tree (with root node root), a target node,
and an integer value k.

Return a list of the values of all nodes that have a distance k
from the target node.  The answer can be returned in any order.


"""


from typing import List

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:

        res = []
        parents = {}

        # find all parent nodes
        def dfs(node):

            if node is None:
                return False, -1
            # found the node
            if node.val == target.val:
                parents[node.val] = (node, 0)
                return True, 0

            # check children have the node or not
            left, left_dist = dfs(node.left)
            right, right_dist = dfs(node.right)

            if left is True:
                parents[node.val] = (node, left_dist+1)
                return True, left_dist+1
            elif right is True:
                parents[node.val] = (node, right_dist+1)
                return True, right_dist+1

            # neither the node nor a parent
            return False, -1

        dfs(root)

        def find(node, distance):
            if node is None or node.val in parents:
                return
            if not distance and node and node.val not in parents:
                res.append(node.val)
            find(node.left, distance-1)
            find(node.right, distance-1)

        for number in parents:
            node, dist = parents[number]
            if k == dist:
                res.append(node.val)
            elif dist < k:
                find(node.left, k-dist-1)
                find(node.right, k-dist-1)

        return res


sol = Solution()

a0 = TreeNode(0)
a1 = TreeNode(1)
a2 = TreeNode(2)
a3 = TreeNode(3)
a4 = TreeNode(4)
a5 = TreeNode(5)
a6 = TreeNode(6)
a7 = TreeNode(7)
a8 = TreeNode(8)

a3.left = a5
a3.right = a1
a5.left = a6
a5.right = a2
a1.left = a0
a1.right = a8
a2.left = a7
a2.right = a4

b0 = TreeNode(0)
b1 = TreeNode(1)
b2 = TreeNode(2)
b3 = TreeNode(3)
b4 = TreeNode(4)
b5 = TreeNode(5)

b0.left = b1
b0.right = b2
b1.right = b3
b2.right = b5
b3.left = b4

print(sol.distanceK(b0, b3, 3))



"""
863
all nodes distance k in binary tree
medium

We are given a binary tree (with root node root), a target node,
and an integer value k.

Return a list of the values of all nodes that have a distance k
from the target node.  The answer can be returned in any order.


"""


from typing import List

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:

        res = []
        parents = {}

        # find all parent nodes
        def dfs(node):

            if node is None:
                return False, -1
            # found the node
            if node.val == target.val:
                parents[node.val] = (node, 0)
                return True, 0

            # check children have the node or not
            left, left_dist = dfs(node.left)
            right, right_dist = dfs(node.right)

            if left is True:
                parents[node.val] = (node, left_dist+1)
                return True, left_dist+1
            elif right is True:
                parents[node.val] = (node, right_dist+1)
                return True, right_dist+1

            # neither the node nor a parent
            return False, -1

        dfs(root)

        def find(node, distance):
            if node is None or node.val in parents:
                return
            if not distance and node and node.val not in parents:
                res.append(node.val)
            find(node.left, distance-1)
            find(node.right, distance-1)

        for number in parents:
            node, dist = parents[number]
            if k == dist:
                res.append(node.val)
            elif dist < k:
                find(node.left, k-dist-1)
                find(node.right, k-dist-1)

        return res


sol = Solution()

a0 = TreeNode(0)
a1 = TreeNode(1)
a2 = TreeNode(2)
a3 = TreeNode(3)
a4 = TreeNode(4)
a5 = TreeNode(5)
a6 = TreeNode(6)
a7 = TreeNode(7)
a8 = TreeNode(8)

a3.left = a5
a3.right = a1
a5.left = a6
a5.right = a2
a1.left = a0
a1.right = a8
a2.left = a7
a2.right = a4

b0 = TreeNode(0)
b1 = TreeNode(1)
b2 = TreeNode(2)
b3 = TreeNode(3)
b4 = TreeNode(4)
b5 = TreeNode(5)

b0.left = b1
b0.right = b2
b1.right = b3
b2.right = b5
b3.left = b4

print(sol.distanceK(b0, b3, 3))
863 all nodes distance k in binary tree medium  We are given a binary tree (with root node root), a target node, and an integer value k.  Return a list of the values of all nodes that have a distance k from the target node.  The answer can be returned in any order. # Definition for a binary tree node. # find all parent nodes # found the node # check children have the node or not # neither the node nor a parent