二叉树中的伪回文路径

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

给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。

请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。

示例 1：

输入：root = [2,3,1,3,1,null,1]
输出：2 
解释：上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 [2,3,3] ，绿色路径 [2,1,1] 和路径 [2,3,1] 。
     在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ，绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。

示例 2：

输入：root = [2,1,1,1,3,null,null,null,null,null,1]
输出：1 
解释：上图为给定二叉树。总共有 3 条从根到叶子的路径：绿色路径 [2,1,1] ，路径 [2,1,3,1] 和路径 [2,1] 。
     这些路径中只有绿色路径是伪回文路径，因为 [2,1,1] 存在回文排列 [1,2,1] 。

示例 3：

输入：root = [9]
输出：1

提示：

给定二叉树的节点数目在范围 [1, 10⁵] 内
1 <= Node.val <= 9

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int pseudoPalindromicPaths (TreeNode* root) { } };

php 解法, 执行用时: 260 ms, 内存消耗: 105 MB, 提交时间: 2023-11-25 00:09:28

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function pseudoPalindromicPaths ($root) {
        $this->ans = 0;
        $this->trav($root, []);
        return $this->ans;
    }

    function trav($root, $map)
    {
        if (!$root) return;
        if (isset($map[$root->val])) $map[$root->val]++;
        else $map[$root->val] = 1;
        if ($map[$root->val] == 2) unset($map[$root->val]);
        if (!$root->left && !$root->right) {
            if (count($map) < 2) {
                $this->ans++;
                return;
            }
        }
        $this->trav($root->left, $map);
        $this->trav($root->right, $map);
    }
}

cpp 解法, 执行用时: 304 ms, 内存消耗: 175.2 MB, 提交时间: 2022-11-29 14:36:40

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int res = 0;
    
    void dfs(TreeNode* node, vector<int>& cnt) {
    	if (!node)
    		return;
    	cnt[node->val]++;
    	if (!node->left && !node->right)
    	{
    		int even = 0;
    		for (int num : cnt) {
    			if (num % 2 == 1)
    				even++;
    		}
    		if (even <= 1)
    			res++;
    	}
    	dfs(node->left, cnt);
    	dfs(node->right, cnt);
    
    	cnt[node->val]--;
    }
    
    int pseudoPalindromicPaths(TreeNode* root) {
    	vector<int> v(10);
    	dfs(root, v);
    	return res;
    }
};

golang 解法, 执行用时: 228 ms, 内存消耗: 22.9 MB, 提交时间: 2022-11-29 14:35:44

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func numberOfOne(num int)int{
    count := 0
    for num != 0{
        count ++
        num = (num - 1) & num
    }
    return count
}

func pseudoPalindromicPaths (root *TreeNode) int {
    var dfs func(record int, root *TreeNode)
    ans := 0

    dfs = func(record int, root *TreeNode){
        if root != nil{
            record ^= (1 << root.Val)
            if root.Left == nil && root.Right == nil{
                if numberOfOne(record) < 2{
                    ans ++
                }
                return
            }
            dfs(record, root.Left)
            dfs(record, root.Right)
        }
    }
    dfs(0, root)    
    return ans
}

python3 解法, 执行用时: 652 ms, 内存消耗: 85.9 MB, 提交时间: 2022-11-29 14:35:16

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:
        self.ans = 0

        def dfs(record, root):
            if root:
                record ^= (1 << root.val)
                if not(root.left or root.right):
                    if bin(record).count("1") < 2:
                        self.ans += 1
                    return
                dfs(record, root.left)
                dfs(record, root.right)
            
        dfs(0, root)
        return self.ans

python3 解法, 执行用时: 724 ms, 内存消耗: 87.1 MB, 提交时间: 2022-11-29 14:35:00

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pseudoPalindromicPaths(self, root: TreeNode) -> int:
        self.res = 0
        if not root:
            return 0

        def get1bit(n):
            # 计算一个数字1的位数
            res = 0
            while n:
                n &= n - 1
                res += 1
            return res

        def dfs(node, mask):
            if not node.left and not node.right:
                # 叶子节点, 且奇数个数的元素数目不大于1就是满足条件的路径
                if get1bit(mask) <= 1:
                    self.res += 1
                return
            if node.left:
                dfs(node.left, mask ^ (1 << node.left.val))
            if node.right:
                dfs(node.right, mask ^ (1 << node.right.val))

        dfs(root, 1 << root.val)
        return self.res

python3 解法, 执行用时: 772 ms, 内存消耗: 85.8 MB, 提交时间: 2022-11-29 14:34:41

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pseudoPalindromicPaths(self, root: TreeNode) -> int:
        self.res = 0
        if not root:
            return 0

        # 把集合移入和移出操作提取出来, 简化代码
        def changeset(oddsets, v):
            if v in oddsets:
                oddsets.remove(v)
            else:
                oddsets.add(v)

        def dfs(node, oddsets):
            if not node.left and not node.right:
                # 叶子节点, 且奇数个数的元素数目不大于1就是满足条件的路径
                if len(oddsets) <= 1:
                    self.res += 1
                return
            if node.left:
                # 注意每次改变集合状态后, 在dfs遍历完要恢复成原始状态, 避免对后面的遍历产生影响, 下同
                changeset(oddsets, node.left.val)
                dfs(node.left, oddsets)
                changeset(oddsets, node.left.val)
            if node.right:
                changeset(oddsets, node.right.val)
                dfs(node.right, oddsets)
                changeset(oddsets, node.right.val)

        dfs(root, {root.val})
        return self.res

java 解法, 执行用时: 7 ms, 内存消耗: 66.7 MB, 提交时间: 2022-11-29 14:32:52

/**
 * 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;
 *     }
 * }
 */
class Solution {
    int ans = 0;
    public int pseudoPalindromicPaths (TreeNode root) {
        if (root == null) return 0;
        int nums = 0;
        dfs(root, nums);
        return ans;
    }

    public void dfs(TreeNode root, int temp) {
        int n = temp ^ (1 << root.val);
        if (root.left == null && root.right == null) {
            if (n == 0 || (n & (n - 1)) == 0) {
                ++ans;
            }
            return;
        }
        if (root.left != null) {
            dfs(root.left, n);
        }
        if (root.right != null) {
            dfs(root.right, n);
        }
    }
}

上一题

下一题

详情