Solve binary-tree reverse printing and LPS

You are given a binary tree node definition:

• TreeNode { int val; TreeNode left; TreeNode right; }

Answer the following two algorithmic questions.

1) Reverse-print a binary tree

Implement a function that returns the values of the tree level by level from bottom to top.

• Input: root (possibly null)
• Output: a list of levels, where each level is a list of node values
• Order requirement: within each level, nodes are listed from left to right, but the levels are returned in reverse (deepest level first).

Example

Tree:

• 1
  • left: 2 (children: 4, 5)
  • right: 3 (right child: 6)

Output: [[4,5,6],[2,3],[1]]

2) Longest palindromic subsequence (LPS)

Given a string s, return the length of the longest subsequence of s that is a palindrome.

• A subsequence keeps relative order but may delete characters.
• Input: string s
• Output: integer length

Example

• Input: "bbbab"
• Output: 4 (one LPS is "bbbb")

Constraints (assume typical interview constraints)

• 0 <= number_of_nodes <= 10^5 for the tree
• 1 <= |s| <= 2000 for LPS