1457. Pseudo-Palindromic Paths in a Binary Tree Medium

1/**
2 * [1457] Pseudo-Palindromic Paths in a Binary Tree
3 *
4 * 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.
5 * Return the number of pseudo-palindromic paths going from the root node to leaf nodes.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2020/05/06/palindromic_paths_1.png" style="width: 300px; height: 201px;" />
9 * 
10 * Input: root = [2,3,1,3,1,null,1]
11 * Output: 2 
12 * 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).
13 * 
14 * Example 2:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2020/05/07/palindromic_paths_2.png" style="width: 300px; height: 314px;" />
16 * 
17 * Input: root = [2,1,1,1,3,null,null,null,null,null,1]
18 * Output: 1 
19 * 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).
20 * 
21 * Example 3:
22 * 
23 * Input: root = [9]
24 * Output: 1
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	The number of nodes in the tree is in the range [1, 10^5].
30 * 	1 <= Node.val <= 9
31 * 
32 */
33pub struct Solution {}
34use crate::util::tree::{TreeNode, to_tree};
35
36// problem: https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/
37// discuss: https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41// Definition for a binary tree node.
42// #[derive(Debug, PartialEq, Eq)]
43// pub struct TreeNode {
44//   pub val: i32,
45//   pub left: Option<Rc<RefCell<TreeNode>>>,
46//   pub right: Option<Rc<RefCell<TreeNode>>>,
47// }
48// 
49// impl TreeNode {
50//   #[inline]
51//   pub fn new(val: i32) -> Self {
52//     TreeNode {
53//       val,
54//       left: None,
55//       right: None
56//     }
57//   }
58// }
59use std::rc::Rc;
60use std::cell::RefCell;
61impl Solution {
62    pub fn pseudo_palindromic_paths (root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
63        0
64    }
65}
66
67// submission codes end
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn test_1457() {
75    }
76}
77