1457. Pseudo-Palindromic Paths in a Binary Tree

The question seems to make it clear we need to check if each route from root to leaf node has
any pseudo-palindromic.

In my first approach

1. I was only interested in keeping the list of each route
2. Now check if any of this list is pseudo-palindromic.

The code below makes it easy without considering the constraints of this question
The number of nodes in the tree is in the range [1, 10^5].
Well this code works for all the test cases provided except the larger input set.
The twodArra is to hold the routes 2D list.

  List<List<Integer>> twodArra= new ArrayList<>();
    public int pseudoPalindromicPathsTLE (TreeNode root) {
        int path[] = new int[1000];
        dfs(root, path, 0);
        int ttAn=  getPseudoPalindromeCount();
        return ttAn;
    }

counting the pseudo palindromes getPseudoPalindromeCount

The code below does it for us with our twodArra global array.

private int getPseudoPalindromeCount() {
        int ttAn =0;
        for (List<Integer> ls : twodArra) {
            Map<Integer,Integer> mp = new HashMap<>();
            for (Integer num : ls) {
                mp.merge(num,1,Integer::sum);
            }
            int count=0;
            for (Map.Entry kev:mp.entrySet()) {
                count+= ((int)kev.getValue()%2);
            }
            if(count<=1) ttAn++;

        }
        return ttAn;
    }

getting routes

Our call to the depth first search is to return all the routes available.

  void dfs(TreeNode node, int path[], int pathLen){
        if (node == null)
            return;
        path[pathLen] = node.val;
        pathLen++;
        if (node.left == null && node.right == null){
        makeList(path, pathLen);}
        else {

            dfs(node.left, path, pathLen);
            dfs(node.right, path, pathLen);
        }
    }

private void makeList(int ints[], int len){
        List<Integer> stack = new ArrayList<>();
        int i;
        for (i = 0; i < len; i++)
        stack.add(ints[i]);

        twodArra.add(stack);

        }

TLE Reason

The code above already has complexity of n^2 with the nested for-loops.
There is no way it would work for search constraints.

Better approach found

The code is using sets to keep track of nodes values.

why??

Because in all case the remaining values of palindrome should be the middle or none.
if both sides are equal.
The above approach used TLE was only using just logical sequence to solve the problem.

public int pseudoPalindromicPaths (TreeNode root) {
        return dfs(root,new HashSet());
    }

Here is the depth search we add values to the set and remove them if found in the route. at the end(leaf node),
we check the sets remainder. if it is palindrome then ofcourse we can have same numbers set or 1 middle remainder.
The call stack check at the leaf nodes keeps returning 1 if the route is pseudo-palindromic or zero if not.

 private int dfs(TreeNode node,Set<Integer> numbers){
        if(node==null) return 0;
        if(numbers.contains(node.val)){
            numbers.remove(node.val);
        }else{
            numbers.add(node.val);
        }
        if(node.left==null&& node.right==null){
            return numbers.size()<=1?1:0;
        }
        int left=dfs(node.left,new HashSet(numbers));
        int right=dfs(node.right,new HashSet(numbers));
        return left+right;
    }

Summary

Sometimes logic sequence works but it fails to fall in the constraints simple tricks are better.