1 class Solution {

 2 public:

 3     TreeNode* r1;TreeNode* r2;

 4     bool isCousins(TreeNode* root, int x, int y) {

 5         dfs(root,r1,x);

 6         dfs(root,r2,y);

 7         int h_x = Depth(root,x);

 8         int h_y = Depth(root,y);

 9         if(h_x == h_y && r1 != r2) return true;

10         return false;

11     }

12     void dfs(TreeNode* root,TreeNode* &r,int v){

13         if(root!= NULL) {

14             dfs(root->left,r,v);

15             if(root->left &&root->left->val == v ) r = root;

16             if(root->right && root->right->val == v) r = root;

17             dfs(root->right,r,v);

18         }

19     }

20     int Depth(TreeNode* root,int v){

21         if(root == NULL) return -1;

22         if(root->val == v) return 0;

23         //TreeNode* node;

24         queue<TreeNode*>q;

25         q.push(root);

26         int depth = 0;

27         while(!q.empty()){

28             int num = q.size(); //一定要有这句，否则会影响下面循环次数

29             for(int i = 0;i < num;i++){

30                 TreeNode* node = q.front();q.pop();

31                 if(node->val == v) return depth;

32                 if(node->left != NULL) q.push(node->left);

33                 if(node->right != NULL) q.push(node->right);

34             }

35             depth++;

36         }

37         return depth;

38     }

39 };