1609. Even Odd Tree #

Problem #

A binary tree is named Even-Odd if it meets the following conditions:

• The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
• For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
• For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

Example 1:

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: true
Explanation: The node values on each level are:
Level 0: [1]
Level 1: [10,4]
Level 2: [3,7,9]
Level 3: [12,8,6,2]
Since levels 0 and 2 are all odd and increasing and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.

Example 2:

Input: root = [5,4,2,3,3,7]
Output: false
Explanation: The node values on each level are:
Level 0: [5]
Level 1: [4,2]
Level 2: [3,3,7]
Node values in level 2 must be in strictly increasing order, so the tree is not Even-Odd.

Example 3:

Input: root = [5,9,1,3,5,7]
Output: false
Explanation: Node values in the level 1 should be even integers.

Example 4:

Input: root = [1]
Output: true

Example 5:

Input: root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
Output: True

Constraints:

• The number of nodes in the tree is in the range [1, 100000].
• 1 <= Node.val <= 1000000

Problem Summary #

If a binary tree satisfies the following conditions, it can be called an Even-Odd Tree:

• The level index of the root node of the binary tree is 0, the level index of the root’s child nodes is 1, the level index of the root’s grandchildren is 2, and so on.
• All node values on even-indexed levels are odd integers and are in strictly increasing order from left to right.
• All node values on odd-indexed levels are even integers and are in strictly decreasing order from left to right.

Given the root node of a binary tree, return true if the binary tree is an Even-Odd Tree; otherwise, return false.

Solution Approach #

• Breadth-first traversal (separately check odd levels and even levels)

Code #

package leetcode

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}

func isEvenOddTree(root *TreeNode) bool {
	level := 0
	queue := []*TreeNode{root}
	for len(queue) != 0 {
		length := len(queue)
		var nums []int
		for i := 0; i < length; i++ {
			node := queue[i]
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
			nums = append(nums, node.Val)
		}
		if level%2 == 0 {
			if !even(nums) {
				return false
			}
		} else {
			if !odd(nums) {
				return false
			}
		}
		queue = queue[length:]
		level++
	}
	return true
}

func odd(nums []int) bool {
	cur := nums[0]
	if cur%2 != 0 {
		return false
	}
	for _, num := range nums[1:] {
		if num >= cur {
			return false
		}
		if num%2 != 0 {
			return false
		}
		cur = num
	}
	return true
}

func even(nums []int) bool {
	cur := nums[0]
	if cur%2 == 0 {
		return false
	}
	for _, num := range nums[1:] {
		if num <= cur {
			return false
		}
		if num%2 == 0 {
			return false
		}
		cur = num
	}
	return true
}