100_相同的树

风扫地

1. /*
   
2. 给定两个二叉树，编写一个函数来检验它们是否相同。
   
3. 
   
4. 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
   
5. 
   
6. 示例 1:
   
7. 
   
8. 输入:       1         1
   
9.           / \       / \
   
10.          2   3     2   3
    
11. 
    
12.         [1,2,3],   [1,2,3]
    
13. 输出: true
    
14. 示例 2:
    
15. 
    
16. 输入:      1          1
    
17.           /           \
    
18.          2             2
    
19. 
    
20.         [1,2],     [1,null,2]
    
21. 输出: false
    
22. 示例 3:
    
23. 输入:       1         1
    
24.           / \       / \
    
25.          2   1     1   2
    
26. 
    
27.         [1,2,1],   [1,1,2]
    
28. 输出: false
    
29. */
    

复制代码

风扫地

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     struct TreeNode *left;
   
6. *     struct TreeNode *right;
   
7. * };
   
8. */
   
9. 
   
10. bool ret_val = true;
    
11. void equalJudag(struct TreeNode* p, struct TreeNode* q)
    
12. {
    
13.    
    
14.     if(  (p==NULL)
    
15.        &&(q==NULL)
    
16.     )
    
17.     {
    
18.         return ;
    
19.     }
    
20.    
    
21.     if((p== NULL)&&(q!=NULL))
    
22.     {
    
23.         ret_val = false;
    
24.         return ;
    
25.     }
    
26.    
    
27.     if((p!=NULL)&&(q==NULL))
    
28.     {
    
29.         ret_val = false;
    
30.         return;
    
31.     }
    
32.    
    
33.     if(p->val != q->val)
    
34.     {
    
35.         ret_val = false;
    
36.         return ;
    
37.     }
    
38.     equalJudag(p->left,q->left);
    
39.     equalJudag(p->right,q->right);   
    
40. }
    
41. 
    
42. /*
    
43. * 递归调用
    
44. */
    
45. bool isSameTree(struct TreeNode* p, struct TreeNode* q)
    
46. {
    
47.     ret_val = true;
    
48.     equalJudag(p,q);
    
49.     return ret_val;
    
50. }
    
51. 
    
52. 
    
53. /*
    
54. 方法1:
    
55. 执行用时 :
    
56. 8 ms, 在所有 C 提交中击败了81.40%的用户内存消耗 :7.1 MB, 在所有 C 提交中击败了100.00%的用户
    
57. */
    

复制代码

风扫地

1. /*
   
2. * 方法2:递归调用+局部变量指针访问
   
3. */
   
4. void equalJudag(struct TreeNode* p, struct TreeNode* q,bool* ret_val)
   
5. {
   
6.    
   
7.     if(  (p==NULL)
   
8.        &&(q==NULL)
   
9.     )
   
10.     {
    
11.         return ;
    
12.     }
    
13.    
    
14.     if((p== NULL)&&(q!=NULL))
    
15.     {
    
16.         *ret_val = false;
    
17.         return ;
    
18.     }
    
19.    
    
20.     if((p!=NULL)&&(q==NULL))
    
21.     {
    
22.         *ret_val = false;
    
23.         return;
    
24.     }
    
25.    
    
26.     if(p->val != q->val)
    
27.     {
    
28.         *ret_val = false;
    
29.         return ;
    
30.     }
    
31.     equalJudag(p->left,q->left,ret_val);
    
32.     equalJudag(p->right,q->right,ret_val);   
    
33. }
    
34. 
    
35. bool isSameTree(struct TreeNode* p, struct TreeNode* q)
    
36. {
    
37.     bool ret_val = true;
    
38.     equalJudag(p,q,&ret_val);
    
39.     return ret_val;
    
40. }
    

复制代码

1. 
   
2. /*
   
3. 方法2:
   
4. 执行用时 :4 ms, 在所有 C 提交中击败了95.35%的用户
   
5. 内存消耗 :6.9 MB, 在所有 C 提交中击败了100.00%的用户
   
6. */
   

复制代码

风扫地

迭代访问至今没学会，貌似需要辅助栈空间，没深究。