树的子结构，树的遍历

题目链接-来源：力扣（LeetCode）

输入两棵二叉树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

思路：

由于我们实现并不知道A的具体结构，因此为了不漏过A的任何一个节点，我们必须对A进行遍历。三种遍历中，先序遍历的递归方法最为简单直观，因此我们采用递归的先序遍历作为算法的模板。

  • 根节点：对于A的每个节点（同时也是当前子树的根节点），我们都考虑是否能让其与B的根节点进入判定流程：根据题目规则，空树不是子结构，同时子结构要求节点形状和节点值都相等，因此只有当节点存在并且节点值相等时，我们才进入对B更深一层子树的判定环节。
  • 左子树：当根节点满足要求后，我们再考虑判定左子树，但是这里可以稍微放宽要求，因为只要B的根节点不为空，B的子树如果是空的话，并不影响子结构判定，所以当B的子树为 null 时，我们省略判定，默认此处判定为 true。之后，与根节点一样，考虑节点值相等，才能继续判定当前两个节点的左子树和右子树。
  • 右子树：处理同左子树。
    根据这样的结构完成判定代码，向上层层返回 boolean 参数，对结果取与运算（&&），即可得到结果。

时间复杂度：O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        
        if (A.val == B.val) {
            boolean temp = true;
            if (B.left != null) {
                temp = temp && (A.left != null && A.left.val == B.left.val) && isSubStructure(A.left, B.left); 
            }
            if (B.right != null) {
                temp = temp && (A.right != null && A.right.val == B.right.val) && isSubStructure(A.right, B.right);
            }
            
            if (temp) {
                return true;
            }
        }
        
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
}