剑指offer计划7(搜索与回溯算法简单版)---java

1.1、题目1

剑指 Offer 26. 树的子结构

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、代码

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、代码

/**
 * 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);
    }
}www.bdsoba.com
www.awaedu.com
(0)

相关推荐

  • 450. 删除二叉搜索树中的节点

    # Definition for a binary tree node.'''搜索二叉树,是一个左子树小于根节点小于右子树的特殊二叉树.'''# 这道题使用递归的方法来做,有删除的节点有四种情况,# ...

  • 每日一题 剑指offer(从上往下打印二叉树)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • ​LeetCode刷题实战145:二叉树的后序遍历

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • 迟来的每日se训练

    import java.util.*; //编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前 class ListNode { int val; ListNod ...

  • (1条消息) 万字长文!二叉树入门和刷题看这篇就够了!

    今天是小浩算法 "365刷题计划" 二叉树入门 - 整合篇.本篇作为入门整合篇,已经砍去难度较大的知识点,所有列出的内容,均为必须掌握.因为很长,写下目录: 二叉树是啥 二叉树的最 ...

  • Leetcode 669 修剪二叉搜索树

    Leetcode 669 修剪二叉搜索树 数据结构定义: 给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high.通过修剪二叉搜索树,使得所有节点的值在[low, high] ...

  • 编程语言剑指offer计划28(搜索与回溯算法困难)---java

    1.1.题目1 剑指 Offer 37. 序列化二叉树 1.2.解法 这题给我笑死了,我看到题解有个解法,我愿称之为神. public class Codec { private TreeNode r ...

  • 剑指offer计划5(查找算法中等版)---java

    剑指offer计划5(查找算法中等版)---java 1.1.题目1 剑指 Offer 04. 二维数组中的查找 1.2.解法 其实就是暴力解法的升级版,从最后一行开始判断,通过num当前的大小, 如 ...

  • 编程语言剑指offer计划25(模拟中等)---java

    1.1.题目1 剑指 Offer 29. 顺时针打印矩阵 1.2.解法 常规开头,先判断特殊情况,然后创建四个变量存放矩阵四边的长度限制. 创建res数组存放结果. 循坏开始,遍历完一行或者一列,就将 ...

  • 【剑指Offer】数值的整数次方

    题目描述 给定一个double类型的浮点数base和int类型的整数exponent.求base的exponent次方. 保证base和exponent不同时为0 解法1 最直接的思路,计算base的 ...

  • 【剑指Offer】链表中倒数第k个结点

    题目描述 输入一个链表,输出该链表中倒数第k个结点. 解法 基本思路是使用两个辅助指针p, q,让p先走k - 1步后,p, q两个指针再一起走 这样当p指针走到链表的末尾时,q指针刚好走到的就是倒数 ...

  • 【剑指Offer】反转链表

    题目描述 输入一个链表,反转链表后,输出新链表的表头. 解法1 可以使用三个辅助指针pHead, last,next pHead记录当前节点,last记录上一个节点,next记录下一个节点 首先使用n ...

  • 剑指 Offer 14- I. 剪绳子

    我服了.动态规划杀我. 可以说一说解决动态规划的思路(只做了两三道就总结了emmm) 1.识别动态规划问题 --重叠子问题:大问题可以分为一个个子问题.和分治策略分割的子问题不同(分治问题的子问题是相 ...

  • 剑指offer

    03 数组中重复的数字 public int findRepeatNumber(int[] nums){ //排序后的数组,重复元素必然相邻 Arrays.sort(nums); //结果集 int ...

  • 剑指 Offer 30. 包含min函数的栈

    定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min.push 及 pop 的时间复杂度都是 O(1). 示例:MinStack minStack = ne ...