树的子结构

题目链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/

image.png

题目解析
B是A的子结构，则子结构的根节点可能为树 A 的任意一个节点。需要两个工作，第一个遍历A节点，第二个在遍历A节点的同时和B进行遍历判断比较是否值相同。

public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B==null){
            return false;
        }
        // 判断A和B是否相等，如果不想等就A遍历下一个节点
        return isEqual(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

    //判断A和B是否相等
    private boolean isEqual(TreeNode A, TreeNode B){
        if (B == null){
            return true;
        }

        if (A==null || A.val!=B.val) {
            return false;
        }
        return isEqual(A.left,B.left) && isEqual(A.right,B.right);
    }

复杂度分析
时间复杂度:O(MN):。其中M,N 分别为树 A 和 树 B 的节点数量；先序遍历树 A 占用 O(M) ，每次调用 isEqual(A, B) 判断占用O(N) 。

空间复杂度:O(M)。当树 A 和树 B 都退化为链表时，递归调用深度最大。当 M≤N 时，遍历树 A 与递归判断的总递归深度为 M ；当 M>N 时，最差情况为遍历至树 A 叶子节点，此时总递归深度为 M。