力扣刷题记录day7 搜索与回溯算法（简单）

一、剑指 Offer 26. 树的子结构

解法1：定义一个比较的函数

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public static boolean isSubStructure(TreeNode A, TreeNode B) {
        // 如果B是空子树，直接返回false
        if(B==null){
            return false;
        }
        // 定义一个队列用来遍历
        Queue<TreeNode> nodeList = new LinkedList<>();
        // 根节点入队
        nodeList.offer(A);
        // 当队列不为空时
        while(!nodeList.isEmpty()){
            TreeNode father = nodeList.poll();
            // 节点出队
            // 如果这个出队的节点和要比的节点的值一样，调用checkSame方法。
            // checkSame方法成功，则返回true
            if(father.val==B.val){
                if(checkSame(father,B)){
                    return true;
                }
            }
            // 添加左节点和右节点
            if(father.left!=null){
                nodeList.offer(father.left);
            }
            if(father.right!=null){
                nodeList.offer(father.right);
            }
        }
        return false;
    }
    public static boolean checkSame(TreeNode A, TreeNode B){
        // 如果主树已经遍历完了，B子树还有值待比较，说明一定不是主树的子树
        if(A == null&& B!=null){
            return false;
        }
        // 如果B子树都遍历完了，说明B子树就是主树的子树
        if(B==null){
            return true;
        }
        // 如果值相同，递归左子树和右子树
        if(A.val == B.val){
            if(checkSame(A.left,B.left)&&checkSame(A.right,B.right)){
                return true;
            }

        }else {
            // 如果有一个节点不同，那肯定就不是主树的子树
            return false;
        }
        return false;
    }
}

解法2：解法1的优化

public static boolean isSubStructure(TreeNode A, TreeNode B) {
    if(B==null||A==null){
        return false;
    }
    Queue<TreeNode> nodeList = new LinkedList<>();
    nodeList.offer(A);
    while(!nodeList.isEmpty()){
        TreeNode father = nodeList.poll();
        if(father.val==B.val){
            if(checkSame(father,B)){
                return true;
            }
        }
        if(father.left!=null){
            nodeList.offer(father.left);
        }
        if(father.right!=null){
            nodeList.offer(father.right);
        }
    }
    return false;
}
public static boolean checkSame(TreeNode A, TreeNode B){
    if(A == null&&B!=null){
        return false;
    }
    if(B==null){
        return true;
    }
    if(A.val == B.val){
        return checkSame(A.left, B.left) && checkSame(A.right, B.right);

    }
    return false;
}

解法3：相同思路的标准答案

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. 二叉树的镜像

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

思路：

• 现有一二叉树如下所示

flowchart TB 1((4))-->2((2)) 1((4))-->3((7)) 2((2))-->4((1)) 2((2))-->5((3)) 3((7))-->6((6)) 3((7))-->7((9))

• 保存根节点4的左子节点2，递归其右子节点7，并准备赋值给左子节点。

flowchart TB 1((4))-.->2((2)) 1((4))-->3((7)) 2((2))-->4((1)) 2((2))-->5((3)) 3((7))-->6((6)) 3((7))-->7((9)) style 3 fill:#f9f,stroke:#333,stroke-width:4px

• 保存节点7的左子节点6，递归其右子节点9，并准备赋值给左子节点。

flowchart TB 1((4))-.->2((2)) 1((4))-->3((7)) 2((2))-->4((1)) 2((2))-->5((3)) 3((7))-.->6((6)) 3((7))-->7((9)) style 7 fill:#f9f,stroke:#333,stroke-width:4px

• 保存节点9的左子节点null，递归其右子节点null，并准备赋值给左子节点。

flowchart TB 1((4))-.->2((2)) 1((4))-->3((7)) 2((2))-->4((1)) 2((2))-->5((3)) 3((7))-.->6((6)) 3((7))-->7((9)) 7((9))-.->8((null)) 7((9))-->9((null)) style 9 fill:#f9f,stroke:#333,stroke-width:4px

• 已经遍历到叶子节点之下了，抵达递归出口，返回null，开始遍历之前储存的左子节点，也返回null。回到节点9。

flowchart TB 1((4))-.->2((2)) 1((4))-->3((7)) 2((2))-->4((1)) 2((2))-->5((3)) 3((7))-.->6((6)) 3((7))-->7((9)) 7((9))-->8((null)) 7((9))-.->9((null)) style 7 fill:#f9f,stroke:#333,stroke-width:4px

• 此时，将节点9赋值给其父节点的左子节点，并开始遍历其父节点的右子节点（之前储存的节点6）

flowchart TB 1((4))-.->2((2)) 1((4))-->3((7)) 2((2))-->4((1)) 2((2))-->5((3)) 3((7))-->6((9)) 3((7))-.->7((6)) style 6 fill:#f9f,stroke:#333,stroke-width:4px

• 节点6的遍历过程和上述相同。就这样一直递归，直到整个树完成镜像翻转。

flowchart TB 1((4))-->2((7)) 1((4))-->3((2)) 2((7))-->4((9)) 2((7))-->5((6)) 3((2))-->6((3)) 3((2))-->7((1)) style 1 fill:#f9f,stroke:#333,stroke-width:4px

三、剑指 Offer 28. 对称的二叉树

思路：

1. 和上一题类似，先考虑特殊情况，若根节点为空，直接返回false；
2. 如果根节点不为空，通过函数recur比较左子节点left和右子节点right。
3. 函数recur:
   1. 如果左子节点left和右子节点right都为null，说明已经比较到叶子节点之下了，他俩仍然在递归比较，说明是镜像的。返回true。这是递归出口。否则，继续向下执行。
   2. 如果左字节点left或者右子节点right有一个为null，说明有一个节点已经比完了，另一个还想比，那肯定不是镜像的。直接返回false。这是递归出口。否则，继续向下执行。
   3. 如果左子节点left的值和右子节点的right的值不相同，说明肯定不是镜像的。直接返回false这是递归出口。否则，继续向下执行。
   4. 如果执行到这里，说明当前的left和right目前看起来还是镜像的，但是他们还有子节点需要比。因此向下递归，将left的左子节点和right的右子节点进行比较，将left的右子节点和right的左子节点进行比较。

流程图：

flowchart TB 1((1))-->2((2)) 1((1))-->3((2)) 2((2))-->4((3)) 2((2))-->5((4)) 3((2))-->6((4)) 3((2))-->7((3)) style 1 fill:#f9f,stroke:#333,stroke-width:4px

flowchart TB 1((1))-->2((2)) 1((1))-->3((2)) 2((2))-->4((3)) 2((2))-->5((4)) 3((2))-->6((4)) 3((2))-->7((3)) style 2 fill:#f9f,stroke:#333,stroke-width:4px style 3 fill:#f9f,stroke:#333,stroke-width:4px

flowchart TB 1((1))-->2((2)) 1((1))-->3((2)) 2((2))-->4((3)) 2((2))-->5((4)) 3((2))-->6((4)) 3((2))-->7((3)) style 4 fill:#f9f,stroke:#333,stroke-width:4px style 7 fill:#f9f,stroke:#333,stroke-width:4px

flowchart TB 1((1))-->2((2)) 1((1))-->3((2)) 2((2))-->4((3)) 2((2))-->5((4)) 3((2))-->6((4)) 3((2))-->7((3)) style 2 fill:#f9f,stroke:#333,stroke-width:4px style 3 fill:#f9f,stroke:#333,stroke-width:4px

flowchart TB 1((1))-->2((2)) 1((1))-->3((2)) 2((2))-->4((3)) 2((2))-->5((4)) 3((2))-->6((4)) 3((2))-->7((3)) style 5 fill:#f9f,stroke:#333,stroke-width:4px style 6 fill:#f9f,stroke:#333,stroke-width:4px

flowchart TB 1((1))-->2((2)) 1((1))-->3((2)) 2((2))-->4((3)) 2((2))-->5((4)) 3((2))-->6((4)) 3((2))-->7((3)) style 2 fill:#f9f,stroke:#333,stroke-width:4px style 3 fill:#f9f,stroke:#333,stroke-width:4px

flowchart TB 1((1))-->2((2)) 1((1))-->3((2)) 2((2))-->4((3)) 2((2))-->5((4)) 3((2))-->6((4)) 3((2))-->7((3)) style 1 fill:#f9f,stroke:#333,stroke-width:4px

标准答案：

public static boolean isSymmetric(TreeNode root) {
    return root == null || recur(root.left, root.right);
}
public static 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);
}

总结

广度优先搜索（二叉树的前序打印）用队列，二叉树的镜像，判断是否镜像用递归。