前言
今天找了一到二叉树遍历的应用题，加深一下对二叉树前序遍历的理解
题目
输入两棵二叉树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);
}
}
总结
总的来说，这也是一道二叉树基本功的题目，稍微有点小的变形，但是也没有增加特别多迷幻色彩，主要考察的还是对于二叉树基本操作的掌握和运用，题目不错，推荐一下~
