[二叉树] 树的子结构

前言

今天找了一到二叉树遍历的应用题，加深一下对二叉树前序遍历的理解

题目

树的子结构

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

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

题目拆解

这道题如果从感官上来理解，可以分为两个角度。

1、看看B树是不是A树某一个树杈。
2、拿着B树，能不能作为A树拼图的一部分。

所以，这两个理解角度，不管哪一个，要求都是，看看A里面是否存在一个节点，这个节点和B的根节点值相同，并且，她的左子树和B的左子树完全一样，这个节点的右子树和B的右子树完全一样。

判断标准也就梳理好了，分为三点
1、当前节点的值和B的根节点值一样。
2、当前节点的左子树和B的左子树一样。
3、当前节点的右子树和B的右子树一样。

这种先判断当前节点，在判断左右节点的的算法结构，和前序遍历一毛一样，所以，解题思路也就出来了。

1、从A的根节点开始前序遍历每个节点，判断是否是和B树相同。
2、判断相同的逻辑，从当前遍历的节点开始，判断当前节点，左节点，右节点，是否和B树相应位置相同。

所以，本题目是一道两次前序遍历融合起来的类型。

细节

有几点细节强调一下
1、空集不是任何数的子结构，所以，如果A或B是空树，直接返回false；
2、判断是否相同时，返回成功的情况是B遍历完或者B的所有子树全部和A的子树对应上了。返回失败的情况，是A树遍历完，或者当前节点值不一样，或者子树节点值不一样。

代码

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 按题目要求,空集不是任何树的子结构
        if (A == null || B == null) {
            return false;
        }


        // 从根节点开始比较
        boolean rootRes = isContain(A, B);
        if (rootRes) return true;
        // 再去比较左子树
        boolean leftRes = isSubStructure(A.left, B);
        if (leftRes) return true;
        // 在比较右子树
        boolean rightRes = isSubStructure(A.right, B);
        return rightRes;
    }

    boolean isContain(TreeNode A, TreeNode B) {
        // B已经遍历完,返回true;
        if (B == null) return true;
        // 如果A没了,肯定不可能包含B,返回false;
        if (A == null) return false;
        // 如果节点值不相同,返回false;
        if (A.val != B.val) return false;
        // 如果节点值相同继续向下比较
        // 左右都相同,才返回false
        return isContain(A.left, B.left) && isContain(A.right, B.right);


    }
}

总结

总的来说，这也是一道二叉树基本功的题目，稍微有点小的变形，但是也没有增加特别多迷幻色彩，主要考察的还是对于二叉树基本操作的掌握和运用，题目不错，推荐一下~