leetcode gives 1609 questions a day. Parity Tree Christmas You've made even and odd numbers without BFS sets of templates once ~

Write before

Christmas Eve, very calm, but the small payment is too boring, but it is not sleepy, fortunately to brush the topic, this Saturday is a good day to rest, but since everyone is not sleeping ~then I am also ashamed to sleep, we have this special Christmas, in fact nothing special, after all, we do not recommend the Ocean Festival...

subject

1. Parity Tree

A binary tree can be called a parity tree if it meets the following conditions:
Binary Tree Root Node Layer Subscript 0, Root Child Node Layer Subscript is 
1 ，The root's grandchild node has a layer subscript of 2, and so on.
Values of all nodes on even subscript layer are odd integers, increasing strictly from left to right
 Values of all nodes on the odd subscript layer are even integers, decreasing strictly in order from left to right
 Give you the root node of a binary tree, and if the binary tree is even-odd, return it true ，Otherwise return false . 

Example

Example 1:

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: true
 Interpretation: Node values at each level are:
0 Layer:[1]
1 Layer:[10,4]
2 Layer:[3,7,9]
3 Layer:[12,8,6,2]
This is an even-odd tree because node values on layers 0 and 2 are both odd and strictly increasing, while node values on layers 1 and 3 are both even and strictly decreasing.

Example 2:

Input: root = [5,4,2,3,3,7]
Output: false
 Interpretation: Node values at each level are:
0 Layer:[5]
1 Layer:[4,2]
2 Layer:[3,3,7]
2 The node values on the layer do not satisfy the condition of strict increment, so this is not a parity tree.

Example 3:

Input: root = [5,9,1,3,5,7]
Output: false
 Interpretation: Node values on layer 1 should be even.

Tips

The number of nodes in the tree is in the range [1, 10^5]
1 <= Node.val <= 10^6

thinking

//You just need to remember that all BFS questions can be done by templates
	public void traverse(TreeNode root){
		if (root == null) return ;
		//Initialize queue, add root to queue
		Queue<TreeNode> q = new ArrayDeque<>();
		q.offer(root);
		while (!q.isEmpty()){
			TreeNode cur = q.poll();
			/*Hierarchical traversal code location*/
			System.out.println(root.val);
			/******************/

			if(cur.left!= null){
				q.offer(cur.left);
			}
			if(cur.right!= null){
				q.offer(cur.right);
			}
		}
	}

The above code is a standard binary tree hierarchical traversal framework, from top to bottom, printing the values of each level of binary tree node from left to right. Here you can see if this topic is much simpler. The only difference that increases is whether the current level is odd or even, recorded with an evenvariable, and then whether the even layer decreases and the odd layer increases in turn. When this level of decision is completed, the reversal of the variable evens is the odd level, which is undoubtedly a parity tree if the conditions are satisfied.

code implementation

/**
 * 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 {
    public boolean isEvenOddTree(TreeNode root) {
        boolean even = true;
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offerLast(root);
        while (!q.isEmpty()){
            int pre = even ? 0 : 1000000;
            for (int i = 0 ,n=q.size();i< n;i++){
                TreeNode node = q.pollFirst();
                if (even && (pre >= node.val || node.val %2 == 0)){
                    return false;
                }

                if (!even && (pre <= node.val || node.val % 2 == 1)){
                    return false;
                }

                pre = node.val;

                if (node.left!= null){
                    q.offerLast(node.left);
                }

                if (node.right != null){
                    q.offerLast(node.right);
                }
            }
            even = !even;
        }
        return true;
    }
}

results of enforcement

Write at the end

That's the special story for nearly Double True Christmas.
Can have a good night's sleep and punch in early today's success~
Take a moderate roll tomorrow, because you have to play with important people~
emmm, although busy recently, small payers will try to update one of the basics they've learned recently - sell a shutdown here starting next week.

Last

Daily Progress Point Daily Harvest Point

May all monarchs succeed in their studies and gain

If you think it's good, don't forget it.