剑指 offer day7

剑指 Offer 26. 树的子结构

题目：

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

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

题解：

1、利用队列循环遍历树A，如果找到和节点B相等的节点node，则调用isSubTree函数；

2、isSubTree(P,Q)函数的思路：

? -如果Q为null，则是子树，返回true；

? -如果P为null或者节点P和Q的value值不相等，返回false；

? -其余情况递归调用isSubTree()函数。

    public boolean isSubStructure(TreeNode A, TreeNode B) {
    if (B==null){
    return false;}Queue<TreeNode> queue = new LinkedList<>();queue.add(A);while (!queue.isEmpty()){
    TreeNode node = queue.remove();if (node.left!=null){
    queue.add(node.left);}if (node.right!=null){
    queue.add(node.right);}if (isSubTree(node,B)){
    return true;}}return false;}private static boolean isSubTree(TreeNode P, TreeNode Q) {
    if(Q == null) return true;if(P == null || P.val != Q.val) return false;return isSubTree(P.left, Q.left) && isSubTree(P.right, Q.right);}

剑指 Offer 27. 二叉树的镜像

题目：

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

题解：

官方题解www
由下到上不断的递归交换每个节点的左右子树，当左右子树均为null时则为叶子节点。

    public TreeNode mirrorTree(TreeNode root) {
    if (root == null) {
    return null;}TreeNode left = mirrorTree(root.left);TreeNode right = mirrorTree(root.right);root.left = right;root.right = left;return root;}

剑指 Offer 28. 对称的二叉树

题目：

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

题解：

1、利用二叉树镜像函数 mirrorTree获得镜像node节点；

2、将node节点和root节点输入isSameTree函数中判断是否相同。
错误原因：镜像函数在处理的时候是在root节点进行处理的，会将之前的root覆盖，也就是说最后得到的node和root其实是一棵树的头节点，可以考虑增加一个copyTree()函数，在获得镜像二叉树之前先对二叉树进行深度拷贝。

    public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
    return true;}if (p == null || q == null) {
    return false;}return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}public TreeNode mirrorTree(TreeNode root) {
    if (root == null) {
    return null;}TreeNode left = mirrorTree(root.left);TreeNode right = mirrorTree(root.right);root.left = right;root.right = left;return root;}public boolean isSymmetric(TreeNode root) {
    TreeNode node = mirrorTree(root);return isSameTree(node,root);}

官方题解

递归判断左子树的左孩子和右子树的右孩子是否相等&&左子树的右孩子和右子树的左孩子是否相等。

class Solution {
    public boolean isSymmetric(TreeNode root) {
    return root == null ? true : recur(root.left, root.right);}boolean recur(TreeNode L, TreeNode R) {
    if(L == null && R == null) return true;if(L == null || R == null || L.val != R.val) return false;return recur(L.left, R.right) && recur(L.right, R.left);}
}

哎 第三题报错？怎么办呢？我不想写了！我还不想拖更？哎 ？就这样鸽着！假装我会了！