Leetcode993：二叉树的堂兄弟节点

堂兄弟节点"/>

Leetcode993：二叉树的堂兄弟节点

Leetcode993：二叉树的堂兄弟节点

• 方法1:广度优先遍历(bfs)
• 方法2:深度优先遍历(dfs)

题目描述：
　　１.二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
　　２.如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
　　３.我们给出了 具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

方法1:广度优先遍历(bfs)

思路：
　　昨天夜里12点还没睡，就打开Leetcode瞄了一眼今天的题目，乍一看有了思路就睡去了， 第二天迷迷糊糊写完代码才发现思路有问题。其实这道题目的核心就是遍历树节点，因为x和y是唯一的，就比较简单了，一旦找到x或者y对应的节点，就对他们的深度、父节点进行记录，然后判断他们的深度是否相同，父节点是否不同。
　　昨晚想的是记录父节点有点麻烦，先不考虑。深度的问题要么通过pair加入队列用bfs记录，要么其实可以用bfs层序遍历时加一个for循环就能对某一层（同一深度）的元素进行判断是否同时存在x和y。在下一层的时候再初始化就行，其实深度的问题就解决了。而且注意到可以做一个初始判断，如果根节点是x或者y，可以直接返回false。
　　解决了深度我懒得思考父节点,索性就认为增加一个index,和flag,flag1,flag2用来判断某一层是否找到了x和y,index1和index2表示x和y所处的循环位置.对每一层遍历完后,当且仅当flag1,flag2都为true,index1和index2的差大于1返回true,下次遍历时初始化这些参数.早上写完程序发现我的想法错了,因为尽管能找到 index1和index2的差大于1,能保证是返回true,但是这样在一些例子中容易漏掉解,如x在一个父节点的右子树上,y在他父节点相邻节点的左侧,他们的index差为1但是却返回了false.
　　想到思路错误后就老老实实记录父节点了.反正大思路想到的是Bfs,就继续用这个方法了.
　　bfs问题中涉及到节点扩张，所以每次扩张的时候才能将父节点和子节点建立联系。那么我们每次就都对节点扩张后的元素作为子节点，当前要退休的元素作为父节点node和node->left, node->right就能建立父子联系了.且当前层的节点一开始是root,而之前提过如果根节点是x或者y，可以直接返回false,其实已经对当前节点做了判断,所以每次程序都是对当前队列元素的扩张节点进行判断了,以下是新写的程序:

class Solution {
public:bool isCousins(TreeNode* root, int x, int y) { TreeNode* pa;TreeNode* ma; bool flag1=false;bool flag2=false; queue<TreeNode*>queue;queue.emplace(root);if(root->val==x || root->val==y) return false;while(!queue.empty()){flag1=false; flag2=false;int size=queue.size();for(int i=1;i<=size;i++){TreeNode* node=queue.front();queue.pop();//左节点扩张if(node->left){queue.emplace(node->left);int temp=node->left->val;if(temp==x){pa=node;flag1=true;}else if(temp==y){ma=node;flag2=true;}}//右节点扩张if(node->right){queue.emplace(node->right);int temp=node->right->val;if(temp==x){flag1=true;pa=node;}else if(temp==y){flag2=true;ma=node;}    }            }if(flag1 && flag2 && pa!=ma)return true;        }return false; }
};

方法2:深度优先遍历(dfs)

思路:
　　当dfs和树的三种遍历方式混在一起的时候,很容易造成混乱,在树的dfs遍历问题中,遍历顺序一般属于从上到下一直往左搜索,搜索到底部,然后返回上一层再往右搜索…最后到根节点再往右搜索然后不断向左搜索…重复上面的步骤…其实这种方式就是前序遍历~~~其实从严格意义上来说dfs在涉及到二叉树的遍历问题中就是前序遍历,只不过dfs可以额外构造三叉树,N叉树甚至每一层的子树个数不同的问题
　　下面直接说思路吧,dfs问题既然也是遍历整个树,但是要增加递归返回条件、操作函数.以及决策条件.同时递归的对象就2个,即使用2次递归函数 左子树递归和右子树递归~.
　　操作函数: dfs 找x和y 找到了就存一下他们的位置(层数)和他们父节点的val值(因为val是唯一的,不同的父节点val值不同)
　 递归返回条件: 遇到空节点返回(要么搜到头了,要么根节点为0),或者 x和y都找到了,也返回,说明没必要继续搜索了.
　 决策条件: 根节点的值不同而x和y的位置(层数相同)返回true,否则返回false
　　注意到涉及到后代的val问题,一定要提前判断后代是否非空,不然空节点不存在val,会报错的

class Solution {//定义私有变量int xpos = 0;int ypos = 0;int rootxVal;int rootyVal;
public:bool isCousins(TreeNode* root, int x, int y) { dfs(root,0,x,y);return (xpos==ypos)&&(rootxVal!=rootyVal);          }//递归函数void dfs(TreeNode* root, int pos, int x, int y){//建立递归返回条件if(root==nullptr ||xpos!=0 && ypos!=0)return;//建立操作函数,因为这里只是简单记录,不涉及到撤回操作的~~if(root->left!=nullptr && root->left->val==x || root->right!=nullptr && root->right->val==x){xpos=pos+1;rootxVal=root->val;}if(root->left!=nullptr && root->left->val==y || root->right!=nullptr && root->right->val==y){ypos=pos+1;rootyVal=root->val;}dfs(root->left,pos+1,x,y);dfs(root->right,pos+1,x,y);    }
};