X

LEETCODE 1609. Even Odd Tree 解题思路分析

题目大意:

奇偶树

如果一棵二叉树满足下述几个条件,则可以称为 奇偶树 :

  • 二叉树根节点所在层下标为 0 ,根的子节点所在层下标为 1 ,根的孙节点所在层下标为 2 ,依此类推。
  • 偶数下标 层上的所有节点的值都是 奇 整数,从左到右按顺序 严格递增
  • 奇数下标 层上的所有节点的值都是 偶 整数,从左到右按顺序 严格递减

给你二叉树的根节点,如果二叉树为 奇偶树 ,则返回 true ,否则返回 false 。

示例 1:

输入:root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
输出:true
解释:每一层的节点值分别是:
0 层:[1]
1 层:[10,4]
2 层:[3,7,9]
3 层:[12,8,6,2]
由于 0 层和 2 层上的节点值都是奇数且严格递增,而 1 层和 3 层上的节点值都是偶数且严格递减,因此这是一棵奇偶树。

示例 2:

输入:root = [5,4,2,3,3,7]
输出:false
解释:每一层的节点值分别是:
0 层:[5]
1 层:[4,2]
2 层:[3,3,7]
2 层上的节点值不满足严格递增的条件,所以这不是一棵奇偶树。

示例 3:

输入:root = [5,9,1,3,5,7]
输出:false
解释:1 层上的节点值应为偶数。

示例 4:

输入:root = [1]
输出:true

示例 5:

输入:root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
输出:true

提示:

  • 树中节点数在范围 [1, 105]
  • 1 <= Node.val <= 106

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1609

解题思路分析:

本题题意很清晰,我们要对二叉树每一层上的节点进行顺序扫描。偶数行必须都是奇数并从左至右升序排列,奇数行都是偶数并从左至右降序排列。逐层扫描二叉树最好的方式就是bfs广度优先搜索!

bfs解题时,我们定义一个层数变量,起始为0。逐层扫描时,我们再使用一个变量来记录当前层前一位置上的节点值,当前为偶数层时,如果当前节点值是偶数或者大于等于前节点,直接返回false。反之当前位奇数层时,如果当前节点值是奇数或者小于等于前节点,也直接返回false。当bfs扫描完所有节点后,证明该二叉树为合理奇偶树,返回true。

实现代码:

public boolean isEvenOddTree(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>(); // bfs使用的Queue
    q.offer(root); // 将根节点作为bfs起始点,加入到Queue中
    int level=0; // 初始层数
    while(q.size()>0){ // 开始bfs
        int size=q.size(); // 当前Queue中存在元素个数即是当前层的元素个数
        // 前一节点值。(默认情况下,奇数行是Int最大值,偶数行是0)
        int preNum=level%2==0?0:Integer.MAX_VALUE;
        while(size>0){ // 循环当前行的每一个节点
            TreeNode node=q.poll(); // 从Queue中取出一个节点
            size--; // 当前行元素个数减一
            if(level%2==0){ // 如果是偶数行
                if(node.val%2==0) return false; // 当前元素是偶数,返回false
                if(node.val<=preNum) return false; // 当前元素小于等于前元素,返回false
            }else{ // 如果是奇数行
                if(node.val%2!=0) return false; // 当前元素是奇数,返回false
                if(node.val>=preNum) return false; // 当前元素大于等于前元素,返回false
            }
            preNum=node.val; // 使用当前元素更新前元素
            if(node.left!=null) q.offer(node.left); // 将左子节点加入到Queue
            if(node.right!=null) q.offer(node.right); // 将右子节点加入到Queue
        } // 当前层遍历结束
        level++; // 层数加一
    }
    return true;
}

本题解法执行时间为8ms。

Runtime: 8 ms, faster than 99.31% of Java online submissions for Even Odd Tree.

Memory Usage: 56.1 MB, less than 85.82% of Java online submissions for Even Odd Tree.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1609-even-odd-tree-解题思路分析/
Categories: leetcode
kwantong: