Grokking Tree Coding Patterns for Interviews

0% completed

​

Solution: Path With Given Sequence

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].

Solution

This problem follows the Binary Tree Path Sum pattern. We can follow the same DFS approach and additionally, track the element of the given sequence that we should match with the current node. Also, we can return false as soon as we find a mismatch between the sequence and the node value.

.....

.....

.....

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