572_另一个树的子树

风扫地

1. 
   
2. /*
   
3. 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
   
4. 
   
5. 示例 1:
   
6. 给定的树 s:
   
7. 
   
8.      3
   
9.     / \
   
10.    4   5
    
11.   / \
    
12. 1   2
    
13. 
    
14. 给定的树 t：
    
15. 
    
16.    4
    
17.   / \
    
18. 1   2
    
19. 
    
20. 返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
    
21. 示例 2:
    
22. 给定的树 s：
    
23.      3
    
24.     / \
    
25.    4   5
    
26.   / \
    
27. 1   2
    
28.     /
    
29.    0
    
30. 给定的树 t：
    
31.    4
    
32.   / \
    
33. 1   2
    
34. 返回 false。
    
35. */
    

复制代码

风扫地

1. /*方法1:两重递归遍历*/
   
2. 
   
3. bool isSameTree(struct TreeNode* s, struct TreeNode* t);
   
4. bool JudgeTree(struct TreeNode* s, struct TreeNode* t);
   
5. bool ret_val = false;
   
6. 
   
7. 
   
8. 
   
9. bool isSameTree(struct TreeNode* s, struct TreeNode* t)
   
10. {
    
11.     if(   (s == NULL)
    
12.        && (t == NULL)
    
13.     )
    
14.     {
    
15.         return true;
    
16.     }
    
17.    
    
18.     if(    (s != NULL)
    
19.         && (t != NULL)
    
20.         )
    
21.     {
    
22.         if (s->val == t->val)
    
23.         {
    
24.             return isSameTree(s->left, t->left) && isSameTree(s->right, t->right);  /*左侧优先,短路逻辑优化*/
    
25.         }
    
26.         else
    
27.         {
    
28.             return false;
    
29.         }
    
30.     }
    
31.     else
    
32.     {
    
33.         return false;
    
34.     }
    
35. }
    
36. 
    
37. 
    
38. bool JudgeTree(struct TreeNode* s, struct TreeNode* t)
    
39. {
    
40.    
    
41.     if(  (s==NULL)
    
42.        &&(t==NULL)
    
43.     )
    
44.     {
    
45.         ret_val = true;
    
46.         return true;
    
47.     }
    
48.    
    
49.     if(  (s==NULL)
    
50.        &&(t!=NULL)
    
51.     )
    
52.     {
    
53.         return false;
    
54.     }
    
55.    
    
56.     if(  (s!=NULL)
    
57.        &&(t==NULL)
    
58.     )
    
59.     {
    
60.         return false;
    
61.     }
    
62.    
    
63.     if(  (isSameTree (s       , t))/*根优先,短路逻辑优化*/
    
64.        ||(JudgeTree  (s->left , t))
    
65.        ||(JudgeTree  (s->right, t))
    
66.     )
    
67.     {
    
68.         ret_val = true;
    
69.         return true;
    
70.     }
    
71.     else
    
72.     {
    
73.         return false;
    
74.     }
    
75. }
    
76. 
    
77. bool isSubtree(struct TreeNode* s, struct TreeNode* t)
    
78. {
    
79.     ret_val = false;
    
80.     JudgeTree(s, t);
    
81.     return ret_val;
    
82. }
    

复制代码

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

复制代码