Leetcode 1883 Solution

This article provides solution to leetcode question 1883 (find-distance-in-a-binary-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 1883" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/find-distance-in-a-binary-tree

Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:
        def findpath(node, value, path):
            if not node:
                return False

            if node.val == value:
                path.append(node)
                return True

            if findpath(node.left, value, path):
                path.append(node)
                return True

            if findpath(node.right, value, path):
                path.append(node)
                return True

            return False

        path1 = []
        findpath(root, p, path1)

        path2 = []
        findpath(root, q, path2)

        i = len(path1)
        j = len(path2)

        while i > 0 and j > 0 and path1[i - 1] == path2[j - 1]:
            i -= 1
            j -= 1

        return i + j