面试题18:树的子结构

2020-04-18  本文已影响0人  Kitlen

题目:

输入两棵二叉树A和B,判断B是不是A的子结构。

思路:

链接:用递归实现。抽象为两步:

1)在树A中找到与树B根结点值相等的结点。递归查找,直到在树A中找到和树B根节点相同的结点node
2)判断值相同的两个结点的左右子树是否相同。如果不相同,会重复1)的步骤,找到node才开始判断两结点左右子树是否一致。

实现:

/**
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) {
        //首先判断两个结点值是否相同,若相同,判断左右子树。
        //如果不相同,则继续判断左子树结点和root2值是否相同
        //如果左子树也不相同,则判断右子树结点和root2值是否相同
        //都不相同。返回false
        boolean hasTree = false;
        if (root1 != null && root2 != null) {
            if (root1.val == root2.val) {
                hasTree = doesTree1hasTree2(root1,root2);
            }
            if (!hasTree) {
                hasTree = HasSubtree(root1.left, root2);
            }
            if (!hasTree) {
                hasTree = HasSubtree(root1.right, root2);
            }
        }
        return hasTree;
    }

     /**
    * 左右子树是否相等
    */
    private boolean doesTree1hasTree2(TreeNode root1, TreeNode root2) {
        //如果左子树相同 && 右子树相同,则是子树
        //否则不是子树
        if (root2 == null) {
            return true;
        }

        if (root1 == null) {
            return false;
        }

        if (root1.val != root2.val){
            return false;
        }

        return doesTree1hasTree2(root1.left,root2.left) && doesTree1hasTree2(root1.right, root2.right);
    }
}
上一篇 下一篇

猜你喜欢

热点阅读