993_二叉树的堂兄弟节点

风扫地

1. /*
   
2. 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
   
3. 
   
4. 如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。
   
5. 
   
6. 我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。
   
7. 
   
8. 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。
   
9. 
   
10. 示例1:
    
11.     1
    
12.   2   3
    
13. 4
    
14. 
    
15. 
    
16. 输入:root = [1,2,3,4],x=4,y=3
    
17. 输出:false。
    
18. 
    
19. 示例2:
    
20.     1
    
21.   2   3
    
22.    4   5
    
23. 
    
24. 输入:root=[,2,3,null,4,null,5],x=5,y=4
    
25. 输出:true
    
26. 
    
27. 示例3:
    
28.     1
    
29.   2   3
    
30.    4
    
31.    
    
32.    
    
33. 输入:root=[1,2,3,null,4],x=2,y=3
    
34. 输出:false
    
35. */

复制代码

风扫地

1. typedef struct tag_char
   
2. {
   
3.   int parent_val    ;   /* 存储父亲节点的值*/
   
4.   int level         ;   /* 存储目标节点的在树中的层次数*/
   
5. }char_t;
   
6. 
   
7. void getNodeInfo(   struct TreeNode*    parent_node ,   /*父亲节点指针                    */
   
8.                     struct TreeNode*    cur_node    ,   /*当前节点指针                    */
   
9.                     int                 val         ,   /*目标节点的值                    */
   
10.                     int                 level       ,   /*当前节点在树中的层次数          */
    
11.                     char_t*             char_s          /*指向存储目标节点信息的结构体    */
    
12.                 )
    
13. {
    
14.    
    
15.     /*已到叶子节点*/
    
16.     if(cur_node==NULL)
    
17.     {
    
18.         return ;
    
19.     }
    
20.    
    
21.     /*已经找到目标节点(存储目标节点的相关信息)*/
    
22.     if(cur_node->val == val)
    
23.     {
    
24.         /*只有根节点的父亲节点是NULL,根据堂兄弟节点的定义和二叉树的性质,根节点跟任何其他节点均不要可能是堂兄弟节点*/
    
25.         if(parent_node==NULL)
    
26.         {
    
27.             char_s->parent_val = -1;
    
28.         }
    
29.         else
    
30.         {
    
31.             /*存储父亲节点的值*/
    
32.             char_s->parent_val = parent_node->val;
    
33.         }
    
34.         /*存储目标节点的层次*/
    
35.         char_s->level = level;
    
36.         return ;
    
37.     }
    
38.    
    
39.     /*遍历左子树*/
    
40.     getNodeInfo(cur_node,cur_node->left ,val,level+1,char_s);
    
41.     /*遍历右子树*/
    
42.     getNodeInfo(cur_node,cur_node->right,val,level+1,char_s);
    
43.    
    
44. }
    
45. 
    
46. 
    
47. /* 常规方法:通过遍历获取节点信息,需要两个节点的父节点不一样且在同一层次才算堂兄弟节点*/
    
48. bool isCousins(struct TreeNode* root, int x, int y)
    
49. {
    
50.     bool ret_val  = false;
    
51.     char_t char_x = {-1,-1};
    
52.     char_t char_y = {-1,-1};
    
53.    
    
54.    
    
55.    
    
56.     getNodeInfo(NULL,root,x,0,&char_x);
    
57.     getNodeInfo(NULL,root,y,0,&char_y);
    
58.    
    
59.     if(  ( char_x.parent_val !=-1                   )
    
60.        &&( char_x.level      !=-1                   )
    
61.        &&( char_y.parent_val !=-1                   )
    
62.        &&( char_y.level      !=-1                   )
    
63.        &&( char_x.parent_val != char_y.parent_val   )
    
64.        &&( char_x.level      == char_y.level        )
    
65.     )
    
66.     {
    
67.         ret_val = true;
    
68.     }
    
69.    
    
70.     return ret_val;
    
71. }
    
72. 
    
73. /*
    
74. 执行用时 :4 ms, 在所有 C 提交中击败了90.63%的用户
    
75. 内存消耗 :7.5 MB, 在所有 C 提交中击败了100.00%的用户
    
76. */
    

复制代码