剑指Offer学习 树的子结构

继续

问题

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：约定空树不是任意一个树的子结构）。

理解

想要判断B是不是A的子结构，我们需要去依次遍历比较双方的结点value。这边采用的是递归的思想来解决该问题。
首先将A的根节点与B的根节点比较，

• 若不相等，则继续扫描A的左右子树，
  • A的左子树，与B的根节点比较，
    • 若该子树的根节点与B的根节点相等，则继续遍历该子树的左右子树与B的左右子树是否相等
    • 若不相等，则继续扫描A的子树结点，直到所有结点扫描结束
  • A的右子树，与B的根节点比较，
    • 若该子树的根节点与B根节点相等，则继续遍历双方的左右子树，判断是否相等
    • 若不相等，继续扫描子树
• 若相等，则双方各自分别往其左右子树方向走；判断左右子树结点是否相等

代码

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null)
            return false;
        boolean result = false;
        if(root1.val == root2.val)
            result = Tree1HaveTree2(root1, root2); //若根节点相等，则递归遍历其左右子树
        if(!result)
            result = HasSubtree(root1.left, root2); //若不相等，扫描A的左子树
        if(!result)
            result = HasSubtree(root1.right, root2); //若不相等，扫描A的右子树
        return result;
    }
    public boolean Tree1HaveTree2(TreeNode r1, TreeNode r2) {
        if(r2 == null)   //若B扫描完成，说明A中有结构与B相等
            return true;
        if(r1 == null)   //若A扫描完成，则表示没有子结构与B相等
            return false;
        if(r1.val != r2.val) //根节点不相等，返回false，继续遍历扫描A的左右子树
            return false;
        // 递归扫描在根节点相等时，A、B左右子树的情况
        return Tree1HaveTree2(r1.left, r2.left) && Tree1HaveTree2(r1.right, r2.right);
    }
}