algorithm/leetcode/EvenOddTree.java at master · skyczhao/algorithm · GitHub

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package leetcode;

import utils.TreeNode;
import utils.Trees;

import java.util.Queue;
import java.util.concurrent.LinkedTransferQueue;

/**
 * EvenOddTree
 * https://leetcode-cn.com/problems/even-odd-tree/
 * 1609. 奇偶树
 * https://leetcode-cn.com/problems/even-odd-tree/solution/yan-du-you-xian-bian-li-by-oshdyr-mbsv/
 *
 * @author tobin
 * @since 2021-12-25
 */
public class EvenOddTree {
    public static void main(String[] args) {
        EvenOddTree sol = new EvenOddTree();

        TreeNode root = Trees.fromIntegers(new Integer[]{
                1,
                10, 4,
                3, null, 7, 9,
                12, 8, 6, null, null, 2});
        System.out.println(sol.isEvenOddTree(root));
    }

    public boolean isEvenOddTree(TreeNode root) {
        if (root == null) {
            return false;
        }

        Queue<TreeNode> evenFloor = new LinkedTransferQueue<>();
        Queue<TreeNode> oddFloor = new LinkedTransferQueue<>();

        evenFloor.add(root);
        int currFloor = 0;
        while (!evenFloor.isEmpty() || !oddFloor.isEmpty()) {
            if (currFloor % 2 == 0) { // 偶数层
                TreeNode last = evenFloor.poll();
                if (last.val % 2 != 1) {
                    // 非奇数即错误
                    return false;
                }
                while (!evenFloor.isEmpty()) {
                    // 偶数层的下层即奇数层
                    if (last.left != null) {
                        oddFloor.add(last.left);
                    }
                    if (last.right != null) {
                        oddFloor.add(last.right);
                    }

                    TreeNode curr = evenFloor.poll();
                    if (curr.val % 2 != 1) {
                        // 非奇数即错误
                        return false;
                    }
                    if (curr.val <= last.val) {
                        // 非严格递增即错误
                        return false;
                    }
                    last = curr;
                }
                // 偶数层的下层即奇数层
                if (last.left != null) {
                    oddFloor.add(last.left);
                }
                if (last.right != null) {
                    oddFloor.add(last.right);
                }

            } else { // 奇数层
                TreeNode last = oddFloor.poll();
                if (last.val % 2 != 0) {
                    // 非偶数即错误
                    return false;
                }
                while (!oddFloor.isEmpty()) {
                    // 奇数层的下层即偶数层
                    if (last.left != null) {
                        evenFloor.add(last.left);
                    }
                    if (last.right != null) {
                        evenFloor.add(last.right);
                    }

                    TreeNode curr = oddFloor.poll();
                    if (curr.val % 2 != 0) {
                        // 非偶数即错误
                        return false;
                    }
                    if (curr.val >= last.val) {
                        // 非严格递减即错误
                        return false;
                    }
                    last = curr;
                }
                // 奇数层的下层即偶数层
                if (last.left != null) {
                    evenFloor.add(last.left);
                }
                if (last.right != null) {
                    evenFloor.add(last.right);
                }
            }

            // 累计层数
            currFloor++;
        }
        return true;
    }
}