剑指 Offer 26. 树的子结构

题目

剑指 Offer 26. 树的子结构

题解

一次遍历

//Java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 一开始如果 A 或者 B为空，直接返回false
        // 因为题目约定空树不是任意一个树的子结构
        if (A == null || B == null) return false;

        // 接下来考虑以下几种情况
        // A的根节点 VS B的根节点
        // 1、A的根节点和B的根节点相同情况，依次比较它们的子节点
        // 2、A的根节点和B的根节点不相同情况，A的左子树 VS B的根节点
        // 3、A的根节点和B的根节点不相同情况，A的右子树 VS B的根节点
        return isSub(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

    boolean isSub(TreeNode A,TreeNode B) {
        // A和B 不匹配的情况有很多，我们需要一开始去找它们完全匹配的情况
        // 即遍历完B，直接为null，说明B的全部节点和A的子结构匹配上
        if (B == null) return true;

        // A中的节点为空，但B中的节点不为空，说明不匹配
        if (A == null) return false;

        // A和B都不为空，但数值不同，说明不匹配
        if (A.val != B.val) return false;

        // 此时，当前这个点是匹配的，继续递归判断左子树和右字树是否 分别匹配
        return isSub(A.left,B.left) && isSub(A.right,B.right);
    }
}