《二叉树刷题计划》——相同的树、对称二叉树、另一棵树的子树-蒲公英云

《二叉树刷题计划》——相同的树、对称二叉树、另一棵树的子树

?相同的树

?对称二叉树

?另一棵树的子树

?相同的树

思路：

?如果这两棵树所各自对应的每个结点都相同，那么这两棵树就是相同的树。从根结点开始，然后再递归判断这两棵树各自的左右子树是否相同。只有当这两棵树的左右子树都相同时，才能说明是相同的树。

?而判断左右子树是否相同，又能转换为相应的子问题求解——即左右子树的子树是否相同，就这样从上到下的进行递归判断，在递归的过程就完成了对每个结点的判断。

代码如下：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null) return false;
        if (p != null && q == null) return false;
        if (p == null && q == null) { // 如果代码能走到这里，说明p、q要么都为空，要么都不为空
            return true; // 都为空也认为是相同的
        }
        if (p.val != q.val) return false; // 代码走到这里，说明q、q都不为空
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // 如果两个根结点的左右子结点同时为相同，说明是这两个树是相同的
    }
}

?对称二叉树

思路：

这个题目也其实也是判断树的各自对应结点是否相同，不过这里要判断的结点是呈轴对称分布的。即左子树的左子结点和右子树的右子结点要相同&&左子树的右子结点和右子树的左子结点要相同。

代码：

class Solution {
    // 判断两个结点是否轴对称
    public boolean tmp (TreeNode leftNode, TreeNode rightNode) {
        if (leftNode != null && rightNode == null) return false;
        if (leftNode == null && rightNode != null) return false;
        // 都为空时，也认为相同
        if (leftNode == null && rightNode == null) return true; // 代码能走到这里，说明这两个结点要么都为空要么都不为空
        if (leftNode.val != rightNode.val) return false; // 代码能走到这里，说明两个都不为空
        // 从上到下进行递归，对每个结点都进行了判断
        return tmp(leftNode.left, rightNode.right) && tmp(leftNode.right, rightNode.left);// 当只有当左子树的左子结点和右子树的右子结点相同 && 左子树的右子节点和右子树的左子节点相同的时候，才是轴对称的
    }
    public boolean isSymmetric(TreeNode root) {
        return tmp(root.left, root.right); // 这一步其实就是判断根结点的左子树和右子树是否轴对称
    }
}

?另一棵树的子树

思路：

要判断一个树 subRoot 是不是树Root的子树，那么可以判断 subRoot 是否和树 Root 的任意子树相等。那么就转化成上面的题——判断两个树是否相同

首先我们需要先判断root和subRoot是否相同，然后递归判断root的左子树和subRoot是否相同，接着就是root右子树是否相同，只要有一个相同就说明subRoot是root的一个子树。

那如果都不相同呢？那就判断root子树的子树是否和root相同呀！当递归判断到root的子树都为空时，如果还不相同，就说明subRoot真的不是root的子树。

代码

class Solution {
    // 判断是否是相同的树
public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null) return false;
        if (p != null && q == null) return false;
        if (p == null && q == null) { // 如果代码能走到这里，说明p、q要么都为空，要么都不为空
            return true; // 都为空也认为是相同的
        }
        if (p.val != q.val) return false; // 代码走到这里，说明q、q都不为空
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // 如果两个根结点的左右子结点同时为相同，说明是这两个树是相同的
    }
    //是不是子树 时间复杂度：O(t * s)
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) return false; // 当递归到子树root都为空，说明subRoot一定不是root的子树
        // 判断包括当前结点在内的整个树是否和subRoot相同
        if(isSameTree(root,subRoot)) return true;
        // 判断当前树的左子树是否和subRoot相同
        if(isSubtree(root.left,subRoot)) return true;
        // 判断当前树的左子树是否和subRoot相同
        if(isSubtree(root.right,subRoot)) return true;
        return false; // 如果能走到这里，说明前面三个递归都结束了，如果root从上到下的所有子树没有一个是和subRoot是相同的（如果相同就返回了）,说明subRoot真的不是root的子树
    }
}