剑指 Offer 26. 树的子结构

image.png

主要思路：先用dfs来比较以root1和root2为头节点的子树能不能符合题意，如果不能再去递归引入root1.left和root2的比较，需要知道||，如果前面有一个是true就返回结果，不会继续执行下去
dfs函数是去比较A，B是不是子结构
1：如果B为null,说明已经被匹配完了，肯定返回true
2：如果A==null，说明匹配完了，也没有找到合适的子结构
3：如果A.val！=B.val，说明这部分肯定不是子结构。如果相等，需要去继续比较A的左子树和右子树是不是相等
必须要先比较B是不是为空，因为即使B为null，A也不一定为null
A为null的前提是B不为null，所以一定是false

image.png

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
       if(B==null||A==null) return false;//在递归前，如果有一方为null，说明肯定不存在这样的子结构
       return dfs(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }
    public boolean dfs(TreeNode A,TreeNode B){
        if(B==null) return true;//B的判断必须在最前边,因为很可能出现B为null，但A不为null
  
        if(A==null) return false;//如果B为null，但A不为null，那一定false
        
        if(A.val!=B.val) return false;
        
        return dfs(A.left,B.left)&&dfs(A.right,B.right);//来比较左子树和右子树
    }
}