题目描述

1609. 奇偶树

题解

此题为简单的BFS ，在二叉树的层级遍历的基础上多加了一个奇偶性的条件判断。

代码参考

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
class Solution {
        public boolean isEvenOddTree(TreeNode root) {
            //1.BFS , 层级遍历
            if (root == null) {
                return false;
            }
            if (root.right == null && root.left == null) {
                if (root.val % 2 == 0) {
                    return false;
                }
                return true;
            }
            //多层级场景
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            //层级标记，默认奇数层级
            boolean oddFlag = true;
            while (!queue.isEmpty()) {
                int size = queue.size();
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    list.add(node.val);
                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }
                }
                //check list
                boolean check = oddFlag ? checkOdd(list) : checkEven(list);
                if (!check) {
                    return false;
                }
                oddFlag = !oddFlag;
            }
            return true;
        }

        //奇数层级校验
        private boolean checkOdd(List<Integer> list) {
            for (int i = 0; i < list.size(); i++) {
                //奇数 ，需要递增
                if (list.get(i) % 2 == 0) {
                    return false;
                }
                if (i < list.size() - 1) {
                    if (list.get(i) >= list.get(i + 1)) {
                        return false;
                    }
                }
            }
            return true;
        }

        //偶数层级校验
        private boolean checkEven(List<Integer> list) {
            for (int i = 0; i < list.size(); i++) {
                // 偶数，需要递减
                if (list.get(i) % 2 == 1) {
                    return false;
                }
                if (i < list.size() - 1) {
                    if (list.get(i) <= list.get(i + 1)) {
                        return false;
                    }
                }
            }
            return true;
        }
    }