奇偶树题解

小咪咪 2023-09-26 19:58 71阅读 0赞

## 题目 ##

> 这是leetcode里的一道题，需要考虑的情况也比较多，个人感觉还是很有意思的，一开始看到题目的时候我居然想到是队列加集合的方式来解，而且我还真就用暴力的方式写了一遍。本题使用Java，迭代遍历树。

**原题链接：https://leetcode.cn/problems/even-odd-tree/**

![在这里插入图片描述][71f29477ce214c3ca2aaac0c6276a760.png]

### 示例说明 ###

**示例一**  
![在这里插入图片描述][2b6ddadf53ee4372b32282410af9a5bc.png]

**示例二**  
![在这里插入图片描述][653207c1d92b4c75b77c17281430cc6f.png]

> 根据题目的要求，需要我们判断二叉树每一层节点，与这一层当中节点与节点之间的关系  
> 因为leetcode上判题是oj型的，我们只需要编写一个实现题目要求的方法即可。  
> **LinkedList可作为双端队列使用，实现了Queue接口。**

### Code1 ###

超级无敌法遍历法，拿空间换ac，也就数据量不是很大，不然应该过不了。
    思路：创建一个二维集合，将二叉树的一层节点值存入一个一维集合当中，最后将一维集合存入二维集合中
    	  最后遍历二维集合来进行判断。

/**
     * 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) {
        
        
            // 单节点特判
            if(null == root)
                {
         return true; }
            if((root.val&1) != 1)
                {
         return false; }
            if(null == root.left && null == root.right)
                {
         return true; }
    		
    		// 创建一个二维集合
            List<List<Integer>> arr=new ArrayList<>();
            List<Integer> temp=new ArrayList<>();
    
            TreeNode curEnd=root;
            TreeNode nextEnd=null;
            Queue<TreeNode> continer =new LinkedList<>();
            continer.add(root);
            
            // 每一层的节点入队列
            while(!continer.isEmpty()){
        
                TreeNode node=continer.poll();
    
                temp.add(node.val);
                
                if(node.left != null){
        
                    nextEnd=node.left;
                    continer.add(node.left);
                }
                if(node.right != null){
        
                    nextEnd=node.right;
                    continer.add(node.right);
                }
    
                // 到达一层的最后一个节点
                if(node == curEnd){
        
                    curEnd=nextEnd;
                    arr.add(temp);	// 将一维集合存入二维集合当中，并给一维集合重新申请空间
                    temp=new ArrayList<>();
                }
            }
    
    		// 遍历二维集合的数据，进行判断
            for(int i=0,len=arr.size(); i<len; ++i){
        
                
                int j=1;
                boolean flag=(i%2 == 0);
                int n=arr.get(i).size();
                while(j < n){
        
                    int val_1=arr.get(i).get(j-1);
                    int val_2=arr.get(i).get(j);
                    // 奇数层
                    if(flag == false){
        
                        if(((val_1&1) == 1) || ((val_2&1) == 1) || (val_1 <= val_2)){
        
                            return false;
                        }
                    }//偶数层
                    else{
        
                        if(((val_1&1) != 1) || ((val_2&1) != 1) || (val_1 >= val_2)){
        
                            return false;
                        }
                    }
                    ++j;
                }
                // 单层单个节点的特判
                if(n == 1){
        
                    if(flag == false){
        
                        if((arr.get(i).get(0)&1) == 1)
                            {
         return false; }
                    }else if((arr.get(i).get(0)&1) != 1){
        
                        return false;
                    }
                }
    
            }
    
            return true;
        }
    }

### 运行结果 ###

属实是太暴力了。

![在这里插入图片描述][2d334b6abf6a4a3a9ffe5e46609a5831.png]

### Code2 ###

/**
     * 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) {
        
            // 思路：利用队列获取每一层的节点，使用一个变量来判断当前层是奇数层还是偶数层，并且，进行不同的操作
    		
    		// 单节点特判
            if(null == root)
                {
         return true; }
            if((root.val&1) != 1)
                {
         return false; }
            if(null == root.left && null == root.right)
                {
         return true; }
            
            boolean flag=false;
            int curVal=0;   //快慢指针法，用于每层结点值的两两判断
    
            TreeNode curEnd=root;
            TreeNode nextEnd=null;
            Queue<TreeNode> continer =new LinkedList<>();
            continer.add(root);
            
            while(!continer.isEmpty()){
        
                TreeNode node=continer.poll();
                // 奇数层
                if(flag == true){
        
                    // 判断当前结点是否为偶数，且curVal != 0，才进行当前结点与前一个结点关系的判断
                    if(((node.val&1) == 1) || (curVal != 0 && (curVal <= node.val) ) )
                        {
         return false; }
                }  
                // 偶数层
                else{
        
                    // 判断当前节点的值是否为奇数，且判断当前节点与前一个结点的关系是否满足要求
                    if( ((node.val&1) != 1) || (curVal != 0 && (curVal >= node.val)))
                        {
         return false; }
                }
                curVal=node.val;    // 慢指针获取值
                
                //左右子结点入队列
                if(node.left != null){
        
                    nextEnd=node.left;
                    continer.add(node.left);
                }
                if(node.right != null){
        
                    nextEnd=node.right;
                    continer.add(node.right);
                }
    
                // 到达一层的最后一个节点
                if(node == curEnd){
        
                    curVal=0;   // 延缓第一个结点的判断
                    curEnd=nextEnd; // curEnd指向下一个层的最后一个结点，进行下一个的判断
                    
                    flag=!flag;	// 奇偶层转换
                }
            }
            return true;
        }
    }

### 运行结果 ###

![在这里插入图片描述][81492dbb6de84d67b333aa2c05e6380b.png]

## 结尾 ##

如有疑问，或code还有可以优化的地方，欢迎各位评论区留言。

[71f29477ce214c3ca2aaac0c6276a760.png]: https://img-blog.csdnimg.cn/71f29477ce214c3ca2aaac0c6276a760.png
[2b6ddadf53ee4372b32282410af9a5bc.png]: https://img-blog.csdnimg.cn/2b6ddadf53ee4372b32282410af9a5bc.png
[653207c1d92b4c75b77c17281430cc6f.png]: https://img-blog.csdnimg.cn/653207c1d92b4c75b77c17281430cc6f.png
[2d334b6abf6a4a3a9ffe5e46609a5831.png]: https://img-blog.csdnimg.cn/2d334b6abf6a4a3a9ffe5e46609a5831.png
[81492dbb6de84d67b333aa2c05e6380b.png]: https://img-blog.csdnimg.cn/81492dbb6de84d67b333aa2c05e6380b.png