面试题26. 树的子结构

题目描述：

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

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

例如:
给定的树 A:

给定的树 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

限制：

0 <= 节点个数 <= 10000

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) {
        boolean ans = false;
        //当两个数都不为空的时候才进行比较，不满足条件则直接返回false
        if(A != null && B != null)
        {
            //如果在A中找到与B的根节点相等的节点
            if(A.val == B.val)
            {
                //则判断是否两个节点具有相同的子结构
                ans = isHasSameTreeNode(A, B);
            }
            //如果A中当前遍历到的节点与B的根节点值不相等，或者相等的节点，子结构不相同
            if(!ans)
            {
                //则继续在A中遍历当前节点的左子树节点，以该节点为起点，去判断是否包含B
                ans = isSubStructure(A.left, B);
            }
             //如果还没找到
            if(!ans)
            {
                //则继续在A中遍历当前节点的右子树节点，以该节点为起点，去判断是否包含B
                ans = isSubStructure(A.right, B);
            }
        }
        return ans;
    }
    public boolean isHasSameTreeNode(TreeNode N1, TreeNode N2)
    {
        //如果B已经遍历完了，说明前面的节点都满足，返回true
        if(N2 == null) return true;
        //如果B还没遍历完，A遍历完了，则不满足子树特点，返回false
        if(N1 == null) return false;
        //如果其中一个节点的值不相等，则返回false
        if(N1.val != N2.val) return false;
        //如果根节点的值相等，就去分别比较左右子树是否也都相等，左右子树结构都相同才返回true
        return isHasSameTreeNode(N1.left, N2.left) && isHasSameTreeNode(N1.right, N2.right);
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof

最后编辑于：2020.02.28 21:26:37