vlambda博客
学习文章列表

力扣每日一题:993. 二叉树的堂兄弟节点(简单)

993. 二叉树的堂兄弟节点

分类:

广度优先搜索 简单

题目:

收获:

  • 回顾广度优先搜索

  • 层序遍历

复杂度:

代码:

层序遍历的写法,使用二维数组对应第一列为该节点的父节点与第二列对应深度。整体题目比较简单,稍稍修改广度优先遍历树即可实现~

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:

   bool isCousins(TreeNode* root, int x, int y) {
       //第一列父节点值,第二列深度
       int tree[101][2]={0};
       bool X=false,Y=false;
       //初始化
       tree[root->val][0]=-1;
       tree[root->val][1]=0;
       queue<TreeNode*> q;
       if(x==root->val || y==root->val){
           return false;
      }
       q.push(root);
       while(!q.empty()){
           //如果xy都找到父节点以及深度就退出循环
           if(X && Y)break;
           TreeNode* cur=q.front();
           q.pop();
           if(cur->left!=NULL){
               q.push(cur->left);
               tree[cur->left->val][0]=cur->val;
               tree[cur->left->val][1]=tree[cur->val][1]+1;
               if(cur->left->val==x){
                   X=true;
              }else if(cur->left->val==y){
                   Y=true;
              }
          }
           if(cur->right!=NULL){
               q.push(cur->right);
               tree[cur->right->val][0]=cur->val;
               tree[cur->right->val][1]=tree[cur->val][1]+1;
               if(cur->right->val==x){
                   X=true;
              }else if(cur->right->val==y){
                   Y=true;
              }
          }            
      }
       //判断
       return tree[x][0]!=tree[y][0] && tree[x][1]==tree[y][1];
  }
};


昨天没有更新是因为出现了一种以前没有学习过的数据结构,最近学习一下再进行更新~

先把今天的更新了,之后会出SQL系列以及我的一些读书笔记,包括有《动手学习深度学习》和《如何阅读一本书》等等。

菜鸟阿力
学习笔记,日常积累
10篇原创内容
Official Account