判断两个节点是否是表兄弟

表兄弟"/>

判断两个节点是否是表兄弟

注意啦，是“表兄弟”，不是一个爸爸的那种哦！

由于我比较笨，我想不出来一个用前序遍历或者后序遍历的做法。

好不容易才想到了，用层序遍历。

但是有很多细节很啰嗦！

显然，我们在同一层中，要是找到了指定的两个值，只要这两个值不是亲兄弟，那么就可以return true了。

之前没有这样子写过层序遍历，哎，还是我太水了！

这道题写了一个小时多。

思路形成才10分钟，debug了接近2小时。还是写程序能力不行啊！加油！

这种方法，虽然过了，但是效率比较低，beats 5%而已。

AC code：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isCousins(TreeNode* root, int x, int y) {if(!root) return false;int smaller=min(x,y);int bigger=max(x,y);//其实这句话可以不要，在while里面也有这个。防止是“亲兄弟”的情况if(!root->left||!root->right||(bigger==max(root->left->val,root->right->val))&&smaller==min(root->left->val,root->right->val)) return false;queue<TreeNode*> Q;Q.push(root->right);Q.push(root->left);//把一层的节点都取出来，然后遍历寻找指定的两个值，如果没找到，那么就继续在下一层找。while(!Q.empty()){vector<int> values;vector<TreeNode*> pointers;queue<TreeNode*> temp=Q;while(!temp.empty()) {if(temp.front()!=NULL){if(temp.front()->left&&temp.front()->right){if((smaller==min(temp.front()->left->val,temp.front()->right->val))&&(bigger==max(temp.front()->left->val,temp.front()->right->val))) return false;}values.push_back(temp.front()->val);pointers.push_back(temp.front());}temp.pop();}for(int i=0;i<values.size();i++) cout<<values[i]<<" ";cout<<endl;bool f1=0,f2=0;for(int i=0;i<values.size();i++){if(values[i]==x) f1=1;if(values[i]==y) f2=1;}if(f1&&f2) return true;else if(f1&&!f2||!f1&&f2) return false;else{for(int i=0;i<values.size();i++){if(pointers[i]->left) {Q.push(pointers[i]->left); }if(pointers[i]->right) {Q.push(pointers[i]->right); }}}}return false;}
};

未完待续...