[剑指Offer] Day 07

题目来源:剑指 Offer 26. 树的子结构

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

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

解题思路:如果树A或树B为空则不满足,直接返回。否则判断B是否为A节点的子结构,或A的左(右)子树的子结构。在递归函数中进行判断:如果B节点为空,表明已经匹配完成,返回true;如果B不为空,而A为空,或A、B节点的值不相同,则匹配失败,返回false;如果A、B的值相同则继续比较A、B的左右子树。

时间复杂度:O(N)

空间复杂度:O(1)

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));

    }

    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);

    }
}

题目来源:剑指 Offer 27. 二叉树的镜像

请完成一个函数,输入一个二叉树,该函数输出它的镜像。

解题思路:对树的根节点调用递归函数。递归函数中执行:若节点为空直接返回;否则交换该节点的左右子树,并分别对其调用递归函数,最后返回节点本身。

时间复杂度:O(N)

空间复杂度:O(1)

 
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        return recur(root);

    }

    TreeNode recur(TreeNode root) {
        if (root == null) return null;
        TreeNode tmpNode = root.left;
        root.left = recur(root.right);
        root.right = recur(tmpNode);
        return root;
    }
}

题目来源:剑指 Offer 28. 对称的二叉树

请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

解题思路:如果根节点为空则满足,直接返回,否则将其左右子树传入递归函数。

递归函数执行过程如下:如果传入的两个节点都为空,则判断结束,条件满足;若有一个不为空或者两个节点的值不相同,则判断结束,条件不满足;如果两个节点的值相同,则继续递归调用,分别比较左左与右右、左右与右左是否满足。

时间复杂度:O(N)

空间复杂度:O(1)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return (root == null) || (recur(root.left, root.right));

    }

    boolean recur(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;
        return recur(left.left, right.right) && recur(left.right, right.left);
    }
}
展示评论