剑指 Offer 26. 树的子结构

in with 0 comment

剑指 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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

以 A 树中每个节点为根节点与 B 树对比,分别使用 A 和 B 的左右节点比较,如果 A 的节点为 null 或者 A 节点的值和 B 节点不相等,证明当前树不包含 B 树,如果 B 树的节点为空即证明 B 树存在于当前节点的 A 树,直接返回 true 即可。

代码

/**
 * 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) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }

    public boolean recur(TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}