剑指offer刷题10——搜索与回溯算法（简单）

剑指 Offer 26. 树的子结构

难度 中等

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

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

例如:
给定的树 A:

3 / \ 4 5 / \ 1 2
给定的树 B：

4 / 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

0 <= 节点个数 <= 10000

思路

采用递归判断的方法比较好撸，先序遍历树A的所有节点，判断每个节点的子树是否包含树B

recur(A, B) 函数：

1. 终止条件：

   1. 当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true ；
   2. 当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false ；
   3. 当节点 A 和 B 的值不同：说明匹配失败，返回 false ；

2. 返回值：

   1. 继续判断 A 和 B 的左子节点是否相等，即 recur(A.left, B.left) ；
   2. 判断 A 和 B 的右子节点是否相等，即 recur(A.right, B.right) ；
      isSubStructure(A, B) 函数：

3. 特例处理： 当 树 A 为空 或 树 B 为空 时，直接返回 false ；

4. 返回值： 若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接；

   1. 以 节点 A 为根节点的子树 包含树 BB ，对应 recur(A, B)；
   2. 树 B 是 树 A 左子树 的子结构，对应 isSubStructure(A.left, B)；
   3. 树 B 是 树 A 右子树 的子结构，对应 isSubStructure(A.right, B)；
      以上 2. 3. 实质上是在对树 AA 做 先序遍历 。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        return ( A != NULL && B != NULL) && (helper(A, B)
        || isSubStructure(A->left,B) || isSubStructure(A->right,B));
    }
    bool helper(TreeNode* A, TreeNode* B)
    {
        if( B == NULL ) return true;
        if( A == NULL || A->val != B->val ) return false;
        return helper(A->left, B->left) && helper(A->right, B->right);
    }
};

刚开始想一个函数直接解决，于是有了以下代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if( A == NULL && B == NULL) return false;
        if( B == NULL ) return true;
        if( A == NULL ) return false;
        if( A->val == B->val ) return isSubStructure(A->left, B->left) 
                            && isSubStructure(A->right,B->right);
        else    //即if(A->val != B->val)
            return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};

后来发现一个函数不方便判断当两个节点值不相同时候的情况，我这里写的两个节点值不相同只能继续往下遍历，没有办法知道是在判断A的子树里的值是否和B的子树的值相同这个逻辑里还是在判断A的子树节点值是否与B的根节点的值相同的逻辑里导致了结果与遍历到底层的结果相同，所以这个题必须分成两个函数来写。

剑指 Offer 27. 二叉树的镜像

难度 简单

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

例如输入：

4 / \ 2 7 / \ / \1 3 6 9
镜像输出：

4  /  \ 7   2 / \  / \9  6 3  1

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

限制：

0 <= 节点个数 <= 1000

注意：本题与主站 226 题相同：https://leetcode-cn.com/problems/invert-binary-tree/

思路

先序遍历，回溯反向

1. 终止条件：空树直接返回
2. 递推工作：
   1. 新建节点暂存root的左子节点,防止修改后左子节点丢失
   2. 进入root的右子树返回为root的左子节点
   3. 进入root的左子树返回为root的右子节点

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 /*
    先序遍历，回溯反向
    1.终止条件：空树直接返回
    2.递推工作：
        1.新建节点暂存root的左子节点,防止修改后左子节点丢失
        2.进入root的右子树返回为root的左子节点
        3.进入root的左子树返回为root的右子节点
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root) return root;
        TreeNode* Node = root->left;
        root->left = mirrorTree(root->right);
        root->right = mirrorTree(Node);
        return root;
    }
};

剑指 Offer 28. 对称的二叉树

难度简单226收藏分享切换为英文接收动态反馈

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

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1 / \ 2 2 / \ / \3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1  / \ 2  2  \  \  3   3

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

限制：

0 <= 节点个数 <= 1000

注意：本题与主站 101 题相同：https://leetcode-cn.com/problems/symmetric-tree/

思路

1. 终止条件：
   1. 左右节点均为空，返回true
   2. 左右节点的值不同，返回false
   3. 左右节点只有一节点为空，返回false
2. 递推内容：
   1. 左右节点值相同，进入左节点的左子树与右节点的右子树继续比较，同时，进入左节点的右子树与右节点的左子树继续比较

大佬的思路：
isSymmetric(root) ：

特例处理： 若根节点 root 为空，则直接返回 true 。
返回值： 即 recur(root.left, root.right) ;
recur(L, R) ：

1. 终止条件：
   • 当 L 和 R 同时越过叶节点： 此树从顶至底的节点都对称，因此返回 true ；
   • 当 L 或 R 中只有一个越过叶节点： 此树不对称，因此返回 false ；
   • 当节点 LL 值 ≠节点 R 值： 此树不对称，因此返回 false；
2. 递推工作：
   • 判断两节点 L.left 和 R.right是否对称，即 recur(L.left, R.right) ；
   • 判断两节点 L.right 和 R.left 是否对称，即 recur(L.right, R.left) ；
   • 返回值： 两对节点都对称时，才是对称树，因此用与逻辑符 && 连接。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 /*
    1. 终止条件：
        1. 左右节点均为空，返回true
        2. 左右节点的值不同，返回false
        3. 左右节点只有一节点为空，返回false
    2. 递推内容：
        1. 左右节点值相同，进入左节点的左子树与右节点的右子树继续比较，同时，进入左节点的右子树与右节点的左子树继续比较
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return helper(root->left, root->right);
    }
    bool helper(TreeNode* Left, TreeNode* Right)
    {
        if( Left == NULL && Right == NULL)  return true;
        if( Left == NULL || Right == NULL) return false;
        if( Left->val != Right->val ) return false;
        return helper( Left->left, Right->right) && helper(Left->right, Right->left);
    }
};