1457. 이진 트리의 의사 회문 경로

5336 단어 cppalgorithms

설명



노드 값이 1에서 9까지의 숫자인 이진 트리가 주어집니다. 경로에 있는 노드 값의 순열 중 하나 이상이 회문인 경우 이진 트리의 경로는 의사 회문이라고 합니다.

루트 노드에서 리프 노드로 이동하는 pseudo-palindromic 경로의 수를 반환합니다.

예 1:



Untitled

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:



Untitled

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


제약:


  • 트리의 노드 수가 [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;
        }
    };
    


    복잡성


  • 시간: O(n)
  • 스페이스: O(h)
  • 좋은 웹페이지 즐겨찾기