【刷题】Leetcode 1609.奇偶树

简介: 这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!

Leetcode 1609.奇偶树

题目描述

根据题目信息,我们可以整理出一些基本思路。

  1. 首先我们需要想办法遍历每层数据 其中需要记录二叉树当前深度。
  2. 遍历的过程中进行判断,不符合要求就返回false

基本就需要做到这两大板块就可以完成我们的任务了。重要的是这个过程如何实现:这里我们用到两个常用方法:广度优先搜索 (BFS)和 深度优先搜索(DFS)。下面初步解释一下两种算法:

广度优先搜索(BFS)

广度优先搜索是连通图的一种遍历算法,是很多重要图算法的原型(比如Dijkstra最短路径算法和Prim最小生成树算法)。它是一种盲目搜索法,目的是展开并检查图中的所有节点,进而得到结果。

过程是十分暴力的,不考虑结果的具体位置,直接遍历搜索所有节点,直到找到结果为止。基本过程是从根节点开始,沿着树(图)遍历所有节点,访问完所以节点后算法终止。常使用队列(FIFO)辅助实现BFS算法。

深度优先算法(DFS)

深度优先算法是图论的经典算法,是针对图和树的遍历算法(比如前序遍历,中序遍历,后序遍历)。利用深度优先算法可以产生目标图的对应拓扑排序表,进而方便的解决问题(如最大路径算法)。

其过程简单来说是对一个可能分支进行处理到不能再进行处理为止。如果是死路就返回,返回图中遇见未探索的分支就进行进行处理,直到达到要求。一般使用堆或栈来辅助实现DFS算法。

思路一(BFS)

根据上面的介绍我们可以通过队列来辅助我们进行遍历所有树。

具体分为两个循环嵌套:

  1. 首先外围while 保证访问所有节点,并记录深度。
  2. 内层for循环 负责处理该层所有节点,并将下一层节点存入队列中。

接下来是一些细节:

  1. leve记录层数 (注意从0开始)
  2. prev 记录上一个节点数
  3. value记录当前节点数
  4. prev 处理完每个节点后 需要迭代。
  5. 每层处理结束后 level++
    这两个循环是算法的核心部分, 保证了遍历所有节点.
    来看代码实现(选择使用C++ 比较方便)
class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {
        //建立队列
        queue<TreeNode*> qu;
        //先入根节点
        qu.push(root);
        //设置层数
        int level = 0;
    //开始遍历 队列全为空就结束
        while(!qu.empty()){
          //prev 为前一个节点值 这里进行初始化
          //偶数下标 层上的所有节点的值都是 奇整数,从左到右按顺序严格递增
          //所以 prev设置为最小值
      //奇数下标 层上的所有节点的值都是 偶整数,从左到右按顺序严格递减
          //所以 prev设置为最大值
            int prev = level % 2 == 0 ? INT_MIN : INT_MAX;
            //获取当前层节点个数
            int size = qu.size();
            //进入该层循环
            for(int i = 0 ; i < size ;i++){
        //出队列 得到节点
                TreeNode* node = qu.front();
                qu.pop();
        //获取当前节点值
                int value = node->val;
        //节点值 与 该层数奇偶不符 返回 false
                if(value % 2 == level % 2) return false;
                //偶数下标层 必须满足严格递增 通过当前值与上一个节点值进行判断
                if(level % 2 == 0 && value <= prev) return false;
                //奇数下标层 必须满足严格递减 通过当前值与上一个节点值进行判断
                if(level % 2 == 1 && value >= prev) return false;
        //进行入队列处理
                if(node->left) qu.push(node->left);
                if(node->right) qu.push(node->right);
        //该节点结束 先前节点值迭代
                prev = value;
            }
            //层数增加
            level++;
        }
        //全部满足条件 返回真即可
        return true;
    }
};

来看效果:

过啦!!! 大声欢呼!!!

思路二(DFS)

该思路使用递归,所以有点不太好理解,动态规划好DFS 的混合运算了属于。

我们写出的dfs函数主要完成以下工作:

bool dfs(TreeNode* root,int p)

  1. root 为当前节点 p 为层数 dp[ p ]储存该层最新的数值
  2. 首先判断是否满足基本条件:
    偶数下标 层上的所有节点的值都是 奇 整数,从左到右按顺序 严格递增

     奇数下标 层上的所有节点的值都是 偶 整数,从左到右按顺序 严格递减
     判断递增递减是通过 当前节点值与dp[ p ]的值进行比较
     满足条件就更新dp[ p ] 值

  1. 然后进行下一层的判断
  2. 直到处理完所有数据。
//设置常量 方便使用
const int N = 1e5 + 7;
const int MAX = 0x3f3f3f3f;
class Solution {
public:
  // dp[]数组储存上一个符合要求的值 
    int dp[N + 1];
    bool dfs(TreeNode* root,int p){
      //记录当前节点值
        int value = root->val;
        //奇数下标层 必须满足严格递减 通过当前值与上一个节点值进行判断
        if(p & 1){
            if(value & 1 || value >= dp[p]) return false;
        }
        //偶数下标层 必须满足严格递增 通过当前值与上一个节点值进行判断
        else{
            if(!(value & 1) || value <= dp[p]) return false;
        }
        //满足条件就更新数组值
        dp[p] = value;
        //继续深入处理
        if(root->left && !dfs(root->left,p+1)) return false;
        if(root->right && !dfs(root->right,p+1)) return false;
        //符合要求 返回真
        return true;
    }
    bool isEvenOddTree(TreeNode* root) {
        for(int i = 0;i<N;i+=2) {
            dp[i] = 0;//偶数下标 需要递增所以使用最小值0
            dp[i + 1] = MAX;//奇数下标 需要递增所以使用最小值0
        }
        return dfs(root,0);
    }
};

来看效果:

过啦!!!!!!!!!!!!!!!!!!!

这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!

Thanks♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!

相关文章
|
4天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
4天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
5天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
5天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
5天前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
5天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
5天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
5天前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
5天前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串