1457. 二叉树中的伪回文路径

1457. 二叉树中的伪回文路径

• 难度: medium
• 原始链接: https://leetcode.cn/problems/pseudo-palindromic-paths-in-a-binary-tree
• 标签: dfs

解法一: dfs

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pseudoPalindromicPaths (root *TreeNode) int {
    flag := 0
    var dfs func(node *TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        count := 0
        flag ^= 1 << node.Val
        if node.Left == nil && node.Right == nil {
            if flag == 0 || (flag & (flag - 1)) == 0 {
                count = 1
            }
        } else {
            count = dfs(node.Left) + dfs(node.Right)
        }
        flag ^= 1 << node.Val
        return count
    }
    return dfs(root)
}