树的子结构（Python and C++解法）

题目：

输入两棵二叉树A和B，判断B是不是A的子结构。约定空树不是任意一个树的子结构。B是A的子结构，即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

3
/
4 5
/
1 2
给定的树 B：

4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof

思路：

　　需要分两步完成：

　　第一步：遍历树A 的节点，寻找与树B根节点相等的节点，如果找到了相等的节点，需要转入第二步判断。

　　第二步：对步骤一中找到的相等节点的子节点，进行匹配，A的左子节点与B的左子节点匹配，A的右子节点与B的右子节点进行匹配。

Python解法：

 1 class TreeNode:
 2     def __init__(self, x):
 3         self.val = x
 4         self.left = None
 5         self.right = None
 6 
 7 class Solution:
 8     def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
 9         result = False  # 树A为空或树B为空，空树不是任意一个树的子结构
10         if A is not None and B is not None:
11             if A.val == B.val:  # 找到了与树B根节点相等的节点
12                 result = self.recur(A, B)  # 进行子树匹配
13             if not result:  # 继续遍历树A的左子树,寻找与树B根节点相等的节点
14                 result = self.isSubStructure(A.left, B)
15             if not result:  # 继续遍历树A的右子树,寻找与树B根节点相等的节点
16                 result = self.isSubStructure(A.right, B)
17         return result
18 
19     def recur(self, A, B):
20         if B is None:  # 树B已匹配完成（越过叶子节点）
21             return True
22         if A is None or A.val != B.val:  # 已经越过树A的叶节点，或子结构出现不相等的子节点
23             return False
24         return self.recur(A.left, B.left) and self.recur(A.right, B.right)  # 继续匹配子节点

C++解法：

 1 struct TreeNode {
 2     int val;
 3     TreeNode *left;
 4     TreeNode *right;
 5     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 6 };
 7 
 8 class Solution {
 9 public:
10     bool isSubStructure(TreeNode* A, TreeNode* B) {
11         bool result = false;
12         if (A != NULL && B != NULL) {
13             if (A->val == B->val)
14                 result = recurr(A, B);
15             if (!result)
16                 result = isSubStructure(A->left, B);
17             if (!result)
18                 result = isSubStructure(A->right, B);
19         }
20         return result;
21     }
22     bool recurr(TreeNode *A, TreeNode *B) {
23         if (B == NULL)
24             return true;
25         if (A == NULL || A->val != B->val)
26             return false;
27         return recurr(A->left, B->left) && recurr(A->right, B->right);
28     }
29 };