剑指offer计划7（搜索与回溯算法简单版）---java1.1、题目1

拼搏现实的明天。 2022-09-10 10:14 132阅读 0赞

#  #

## 1.1、题目1 ##

## 1.2、解法 ##

这题看了解法，感叹真的6，代码量减了很多。

(A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));

这一句实现了遍历整个树来寻找二叉树，并，同时加上了判断条件。

而recur函数中，则负责判断两个结点下的二叉树是否相同。

当结点移到null的时候，就证明已经结束，并且目前所经过的值都相同，则返回true

这题答案看了之后：“好像我也会。”

过几天一看：“咋做来着。”

## 1.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);
        }
    }
    
    
    2.1、题目2
    剑指 Offer 27. 二叉树的镜像
    2.2、解法
    其实这几行代码还能再简洁一点，因为left和right没变，可以把交换放在下面，
    
    但是你懂就好啦，hhhhh，这题就是递归下去。
    
    2.3、代码
    
    JAVA
    class Solution {
        public TreeNode mirrorTree(TreeNode root) {
            if(root==null) return null;
            TreeNode left = root.left;
            root.left=root.right;
            root.right=left;
            root.left=mirrorTree(root.left);
            root.right=mirrorTree(root.right);
            return root;
        }
    }
    
    3.1、题目3
    剑指 Offer 28. 对称的二叉树
    3.2、解法
    这题自定义函数RECUR，通过判断null或者值不相同返回false，递归解决。
    
    3.3、代码
    
    
    JAVA
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean isSymmetric(TreeNode root) {
            return root==null?true:recur(root.left,root.right);
        }
        boolean recur (TreeNode a,TreeNode b){
            if(a==null && b==null) return true;
            if(a==null || b==null ||a.val!=b.val)  return false;
            return recur(a.left,b.right) && recur(a.right,b.left);
        }
    }
    
    本文作者：叫我阿康就好
    
    本文链接：https://www.cnblogs.com/urmkhaos/p/15236736.html
    
    版权声明：本作品采用知识共享署名-非商业性使用-禁止演绎 2.5 中国大陆许可协议进行许可。
    
    关注我
    收藏该文
     0
     0
    Posted @ 2021-09-07 09:19  叫我阿康就好  阅读(6)  评论(0)  编辑  收藏  举报
    登录后才能查看或发表评论，立即 登录 或者 逛逛 博客园首页
    【推荐】阿里云云大使特惠：新用户购ECS服务器1核2G最低价87元/年
    【推荐】大型组态、工控、仿真、CAD\GIS 50万行VC++源码免费下载!
    【推荐】百度智能云超值优惠：新用户首购云服务器1核1G低至69元/年
    【推荐】和开发者在一起：华为开发者社区，入驻博客园科技品牌专区
    【推广】园子与爱卡汽车爱宝险合作，随手就可以买一份的百万医疗保险
    Copyright © 2021 叫我阿康就好
    Powered by .NET 5.0 on Kubernetes
    
    目录
    1.1、题目1
    剑指 Offer 26. 树的子结构
    1.2、解法
    1.3、代码
    2.1、题目2
    剑指 Offer 27. 二叉树的镜像
    2.2、解法
    2.3、代码
    3.1、题目3
    剑指 Offer 28. 对称的二叉树
    3.2、解法
    3.3、代码
    
    Autumn Wonderland
    07 Sept, 2021
    Sept
    07
    随笔分类 (9)
    技术分享(1)
    其他后端分享(8)
    阅读排行榜
    1. 剑指offer计划5（查找算法中等版）---java(38)
    2. Git连接github以及gitee等使用教程(34)
    3. Java学习路线(27)
    4. 剑指offer 计划1（栈与队列）---java(21)
    5. 剑指offer计划2（链表）---java(11)
    CNBLOG
    MENU
    博客园
    首页
    新随笔
    联系
    订阅
    管理
    FAVOURITE
    收藏夹
    Fork me on GitHub
    
    叫我阿康就好

## 2.1、题目2 ##

## 2.2、解法 ##

其实这几行代码还能[java教程][java]再简洁一点，因为left和right没变，可以把交换放在下面，

但是你懂就好啦，hhhhh，这题就是递归下去。

## 2.3、代码 ##

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

## 3.1、题目3 ##

## 3.2、解法 ##

这题自定义函数RECUR，通过判断null或者值不相同返回false，递归解决。

## 3.3、代码 ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean isSymmetric(TreeNode root) {
            return root==null?true:recur(root.left,root.right);
        }
        boolean recur (TreeNode a,TreeNode b){
            if(a==null && b==null) return true;
            if(a==null || b==null ||a.val!=b.val)  return false;
            return recur(a.left,b.right) && recur(a.right,b.left);
        }
    }

本文作者：叫我阿康就好

[java]: https://www.xin3721.com/eschool/Javaxin3721/