文章482
标签257
分类63

算法:树的子结构


树的子结构

树的子结构

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)


分析

通过递归进行判断: 如果A当前节点等于B的根节点, 递归判断是否是子树


代码

public class Solution {
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root2 == null || root1 == null) return false;
        return helper(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }

    private boolean helper(TreeNode root1, TreeNode root2) {
        if (root2 == null) return true;
        if (root1 == null) return false;

        if (root1.val == root2.val) return helper(root1.left, root2.left) && helper(root1.right, root2.right);
        return false;
    }
}

本文作者:Jasonkay
本文链接:https://jasonkayzk.github.io/1996/07/27/算法-树的子结构/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可