算法-26.树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。
思路：采用双递归的方式，外层递归在二叉树A中找到与二叉树B的root节点相同的节点，内层递归则是从第一个相同节点开始进行相同方向的遍历操作

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        // 这里使用或运算，当第一个条件不满足的时候执行第二个条件，当第二个条件不满足的时候执行第三个条件
        // 当三个条件都为false的时候，才返回false
        // 第一个条件是判断当前节点是否相同，如果不相同，则返回false
        // 第一个条件不满足时，沿着主树A的左子树开始遍历查询，进行递归，直到找到与B的root节点相同的点
        // 如果第二个条件不满足，说明在A的左子树中也没有找到与B的root节点相同的点，则遍历A的右子树
        return isSubtreeWithRoot(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    public boolean isSubtreeWithRoot(TreeNode A, TreeNode B) {
        // 说明B已经遍历完成，则直接返回true
        if (B == null) {
            return true;
        }
        if (A == null) {
            return false;
        }
        // 找到当前节点相同的，如果当前节点不相同，则返回false
        if (A.val != B.val) {
            return false;
        }
        // 这里采用与运算，即需要两个方向同时进行遍历相同
        return isSubtreeWithRoot(A.left, B.left) && isSubtreeWithRoot(A.right, B.right);
    }