表兄弟"/>
判断两个节点是否是表兄弟
注意啦,是“表兄弟”,不是一个爸爸的那种哦!
由于我比较笨,我想不出来一个用前序遍历或者后序遍历的做法。
好不容易才想到了,用层序遍历。
但是有很多细节很啰嗦!
显然,我们在同一层中,要是找到了指定的两个值,只要这两个值不是亲兄弟,那么就可以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;}
};
未完待续...
更多推荐
判断两个节点是否是表兄弟
发布评论