LeetCode刷题【剑指 Offer 26】树的子结构

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

限制：

0 <= 节点个数 <= 10000

一顿分析

1. 遍历A树的每个节点，找到和B树的头结点值相同的
2. 找到了相同的节点之后，则开始遍历A、B比较值是否相同，如果相同则直接返回true
3. 如果不相等，还得继续遍历A树寻找是否还有节点和B的头结点值相等
4. 更多细节参见代码注释

代码

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //排除掉null节点的情况，以及递归截止调节
        if (A == null || B == null){
            return false;
        }
        //找到了树头结点相等的
        if (A.val == B.val){
            //从这个节点开始往下比较，如果能匹配则直接返回true
            //如果不能匹配，还得继续遍历找其他的节点看有没和B的头结点相等的
            if( comapre(A,B) ) {
                return true;
            }
        }
        //递归往左下和往右下
        //任意一边有返回能匹配上就可以用 || 条件
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    //树比较
    public boolean comapre(TreeNode A, TreeNode B){
        //如果B以及到结尾了，则无论A上此时是啥，都表示能完全匹配上
        if (B == null){
            return true;
        }
        //如果A到结尾了而，B没到结尾，则不能继续匹配了，返回false
        if (A==null){
            return false;
        }
        //A、B都没到结尾，如果不相等的话则直接返回false
        if (A.val != B.val){
            return false;
        }
        //到了这里表示A、B树节点比较目前都是相等的，则继续比较 A左&B左  和 A右&B右
        //两边都要同时满足相等 用 && 条件
        return comapre(A.left,B.left) && comapre(A.right,B.right);
    }
}