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

因为我二叉树建树很烂，建了半天树，特此记录

题目

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

分析

问题很简单，只需要建树，然后维护一个哈希表，dfs的时候记录下每个数字出现的次数，到了叶子节点后（没有左右孩子），遍历该哈希表，如果出现了两次奇数个数字，则说明不能构成回文

如上图例1，深度优先最左边的枝，数字序列为 2 3 3，那么哈希表为 1 2。即2出现了一次，3出现了两次，则可以构成回文 3 2 3

对于 2 3 1 这个遍历，由于哈希表为 1 1 1，即奇数个数字出现了两次以上，则不能构成回文

复盘

关键在于建树不熟练，导致时间慢了

序列为层序遍历的数组

对于第 i 个元素，应该判断他是否有孩子节点，如果有，则给孩子节点创建一个树，使用递归建树

层序遍历的数组，他的左孩子索引为 i * 2 + 1 ，右孩子索引为 (i + 1) * 2

对于左孩子，应有

1
2
3
4
5
6


if (now * 2 + 1 <= n - 1){
    int left = now * 2 + 1;
    TreeNode childLeft = initTree(new TreeNode(), nums, left * 2 + 1);
    TreeNode childRight = initTree(new TreeNode(), nums, (left + 1) * 2));
    tree.left = new TreeNode(nums[now * 2 + 1], childLeft, childRight;
}

这里的 left * 2 + 1 是对于 i 左孩子的左孩子的当前索引

同理可得右孩子递归写法

1
2
3
4
5
6


if ((now + 1) * 2 <= n - 1){
    int right = (now + 1) * 2;
    TreeNode childLeft = initTree(new TreeNode(), nums, right * 2 + 1);
    TreeNode childRight = initTree(new TreeNode(), nums, (right + 1) * 2));
    tree.right = new TreeNode(nums[now * 2 + 1], childLeft, childRight;
}

完整代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70


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 {
    public int pseudoPalindromicPaths (TreeNode root) {
        dfs(root);
        return this.ans;
    }
    int ans = 0;
    int[] hashmap = new int[10];
    public TreeNode initTree(TreeNode tree, int[] nums, int now){
        int n = nums.length;
        if (now >= n || nums[now] == -1)
            return null;
        tree.val = nums[now];
        if (now * 2 + 1 <= n - 1 && nums[now * 2 + 1] != -1){
            tree.left = new TreeNode(nums[now * 2 + 1], initTree(new TreeNode(), nums, (now * 2 + 1) * 2 + 1), initTree(new TreeNode(), nums, (now + 2) * 2));
        }
        // 1 2 3 4 5 6 7
        // 0 1 2 3 4 5 6
        if ((now + 1) * 2 <= n - 1 && nums[(now + 1) * 2] != -1){
            tree.right = new TreeNode(nums[(now + 1) * 2], initTree(new TreeNode(), nums, (now + 1) * 2 * 2 + 1), initTree(new TreeNode(), nums, ((now + 1) * 2 + 1) * 2));
        }
        return tree;
    }

    public void dfs(TreeNode tree){
        if(tree == null){
            return;
        }
        hashmap[tree.val]++;
        dfs(tree.left);
        dfs(tree.right);
        if(tree.left == null && tree.right == null){ // 子叶子节点记录一次
            boolean flag = false, flag1 = false;
            for(int i:hashmap){
                if(flag && i % 2 != 0){
                    flag1 = true;
                    break;
                }
                if(i % 2 != 0){
                    flag = true;
                }
            }
            if(!flag1) // 如果没有遇到两次奇数，则ans++
                ans++;
        }
        hashmap[tree.val]--;
    }
}
public class LC1457 {

    public static void main(String[] args) {
        Solution mysolution = new Solution();
        int[] nums = new int[]{2,3,1,3,1,-1,1};
        TreeNode tree = mysolution.initTree(new TreeNode(), nums, 0);
        System.out.println(mysolution.pseudoPalindromicPaths(tree));
    }
}