LeetCode993. 二叉树的堂兄弟节点

题目

 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 };

注意：

1.依旧是函数的形参为指针情况，如果想要保存对指针的修改需要址传递如dfs中 TreeNode* &r

2.第28行代码别忘记，一定要提前记录每一层的个数