Grokking Tree Coding Patterns for Interviews

0% completed

​

Path With Given Sequence (medium)

Problem Statement

Given a binary tree and a number sequence, find if the sequence is present as a root-to-leaf path in the given tree.

Constraints:

  • 1 <= arr.length <= 5000
  • 0 <= arr[i] <= 9
  • Each node's value is between [0 - 9].

Try it yourself

Try solving this question here:

.....

.....

.....

Like the course? Get enrolled and start learning!
T

Thai Minh

· 3 years ago

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

class Solution:
  def findPath(self, root, sequence):
    # TODO: Write your code here
    return self.findPath_helper(root, sequence, [])
  def findPath_helper(self, root, sequence, currList):
    if root is None:
      return False

    currList.append(root.val)
    print(currList)
    if currList == sequence and root.left is None and root.right is None:
      return True
    exist_left = self.findPath_helper(root.left, sequence, currList)
    exist_right = self.findPath_helper(root.right, sequence, currList)
    del currList[-1]
    return exist_left | exist_right
Kyle Alberry

Kyle Alberry

· 2 years ago

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

class Solution:
  def findPath(self, root, sequence):
    dummy = TreeNode(-1,root)
    cur = dummy
    for num in sequence:
      if cur.left and num == cur.left.val:
        cur = cur.left
      elif cur.right and num == cur.right.val:
        cur = cur.right
      else:
        return False
    if not cur.left and not cur.right:
      return True
    return False