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