1457. 이진 트리의 의사 회문 경로
5336 단어 cppalgorithms
설명
노드 값이 1에서 9까지의 숫자인 이진 트리가 주어집니다. 경로에 있는 노드 값의 순열 중 하나 이상이 회문인 경우 이진 트리의 경로는 의사 회문이라고 합니다.
루트 노드에서 리프 노드로 이동하는 pseudo-palindromic 경로의 수를 반환합니다.
예 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).
예 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).
예 3:
Input: root = [9]
Output: 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).
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).
Input: root = [9]
Output: 1
[1, 105]
범위에 있습니다. 1 <= Node.val <= 9
솔루션
솔루션 1
직관
암호
class Solution {
private:
int res = 0;
void dfs(int mask, TreeNode* node) {
if (!node) return;
mask ^= 1 << node->val;
dfs(mask, node->left);
dfs(mask, node->right);
if (!node->left && !node->right) {
if (mask == 0 || (mask & (mask - 1)) == 0) res++;
}
}
public:
int pseudoPalindromicPaths(TreeNode* root) {
dfs(0, root);
return res;
}
};
복잡성
class Solution {
private:
int res = 0;
void dfs(int mask, TreeNode* node) {
if (!node) return;
mask ^= 1 << node->val;
dfs(mask, node->left);
dfs(mask, node->right);
if (!node->left && !node->right) {
if (mask == 0 || (mask & (mask - 1)) == 0) res++;
}
}
public:
int pseudoPalindromicPaths(TreeNode* root) {
dfs(0, root);
return res;
}
};
Reference
이 문제에 관하여(1457. 이진 트리의 의사 회문 경로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/jiangwenqi/1457-pseudo-palindromic-paths-in-a-binary-tree-jj0텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)