Leetcode Problem 971. Flip Binary Tree To Match Preorder Traversal

971. Flip Binary Tree To Match Preorder Traversal

Leetcode Solutions

Depth-First Search to Match Pre-Order Traversal

  1. Initialize an empty list flipped to record the values of flipped nodes.
  2. Start a DFS traversal from the root node with an index i tracking the current position in voyage.
  3. If the current node is null, return true as a base case.
  4. If the current node's value does not match voyage[i], return false indicating a mismatch.
  5. Increment i to move to the next expected value in voyage.
  6. If the left child exists and its value does not match voyage[i], flip the current node by swapping its left and right children, and add the current node's value to flipped.
  7. Recursively call DFS on the left child.
  8. Recursively call DFS on the right child.
  9. If either recursive call returns false, propagate the false return value up the call stack.
  10. If the traversal completes without mismatches, return flipped; otherwise, return [-1].
UML Thumbnail

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...