1457. Pseudo-Palindromic Paths in a Binary Tree

⭐⭐⭐

題目敘述

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Example 1

Input: root = [2,3,1,3,1,null,1] Output: 2 Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 2

Input: root = [2,1,1,1,3,null,null,null,null,null,1] Output: 1 Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 3

Input: root = [9] Output: 1

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

解題思路

Solution

import java.util.Stack;

class Solution {
    private int ans;

    public int pseudoPalindromicPaths(TreeNode root) {
        ans = 0;
        Stack<Object[]> stack = new Stack<>();
        stack.push(new Object[]{root, 0});

        while (!stack.isEmpty()) {
            Object[] tmp = stack.pop();
            TreeNode curr = (TreeNode) tmp[0];
            int val = (int) tmp[1];

            if(curr != null){
                val = val ^ (1 << curr.val);

                if(curr.left == null && curr.right == null){
                    if((val & (val - 1)) == 0){
                        ans++;
                    }
                }else{
                    stack.push(new Object[]{curr.left, val});
                    stack.push(new Object[]{curr.right, val});
                }
            }
        }

        return ans;
    }
}