代码编织梦想

题目:

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true
示例 2:

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false
示例 3:

输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

解题思路:

前言

两个二叉树相同,当且仅当两个二叉树的结构完全相同,且所有对应节点的值相同。因此,可以通过搜索的方式判断两个二叉树是否相同。

方法一:深度优先搜索

如果两个二叉树都为空,则两个二叉树相同。如果两个二叉树中有且只有一个为空,则两个二叉树一定不相同。

如果两个二叉树都不为空,那么首先判断它们的根节点的值是否相同,若不相同则两个二叉树一定不同,若相同,再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程,因此可以使用深度优先搜索,递归地判断两个二叉树是否相同。

代码

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}

方法二:广度优先搜索

也可以通过广度优先搜索判断两个二叉树是否相同。同样首先判断两个二叉树是否为空,如果两个二叉树都不为空,则从两个二叉树的根节点开始广度优先搜索。

使用两个队列分别存储两个二叉树的节点。初始时将两个二叉树的根节点分别加入两个队列。每次从两个队列各取出一个节点,进行如下比较操作。

比较两个节点的值,如果两个节点的值不相同则两个二叉树一定不同;

如果两个节点的值相同,则判断两个节点的子节点是否为空,如果只有一个节点的左子节点为空,或者只有一个节点的右子节点为空,则两个二叉树的结构不同,因此两个二叉树一定不同;

如果两个节点的子节点的结构相同,则将两个节点的非空子节点分别加入两个队列,子节点加入队列时需要注意顺序,如果左右子节点都不为空,则先加入左子节点,后加入右子节点。

如果搜索结束时两个队列同时为空,则两个二叉树相同。如果只有一个队列为空,则两个二叉树的结构不同,因此两个二叉树不同。

代码

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue1.offer(p);
        queue2.offer(q);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            if (node1.val != node2.val) {
                return false;
            }
            TreeNode left1 = node1.left, right1 = node1.right, left2 = node2.left, right2 = node2.right;
            if (left1 == null ^ left2 == null) {
                return false;
            }
            if (right1 == null ^ right2 == null) {
                return false;
            }
            if (left1 != null) {
                queue1.offer(left1);
            }
            if (right1 != null) {
                queue1.offer(right1);
            }
            if (left2 != null) {
                queue2.offer(left2);
            }
            if (right2 != null) {
                queue2.offer(right2);
            }
        }
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/a12355556/article/details/111097115

算法总结一: Linked List的高频操作-爱代码爱编程

学习目标: 算法总结一: Linked List 学习内容: 1、 Leetcode题库Linked List tag高频题 学习时间: 1、 周一至周天晚上 7 点—晚上9点 学习产出: 1、 技术笔记 1 篇 2、解题思路视频1个 ===================================== linked list的

左神算法基础班 第1章 第一周学习——认识复杂度和简单排序算法-爱代码爱编程

左神算法课基础班 1. 复杂度、对数器、二分法、位运算与异或运算 1.1 排序 1.1.1 Java自带的排序函数 Arrays.sort(arr); 1.1.2 冒泡排序   时间复杂度O(n*n),空间复杂度O(1)1.1.3 选择排序   时间复杂度O(n*n),空间复杂度O(1)保留数组中最小or最大的值的下标1.1.4 插入排序 

[MATLAB]Jacobi迭代-爱代码爱编程

[MATLAB代码]关于使用雅可比迭代法求线性方程组的数值解 jacobi.m %定义Jacobi迭代函数 function [x, n] = jacobi(A, b, x0, eps) %计算迭代矩阵 D = diag(diag(A)); L = -tril(A,-1); U = -triu(A,1); BJ = D\(L+U); f = D\b; %

原地堆排序(不占用额外空间)(C++实现)-爱代码爱编程

原地堆排序,不占用额外空间 // 原地堆排序,不占用额外空间 template<typename T> void shiftDown(T data[], int n, int i) { using uint = unsigned int; uint k = i; whil

leetcode 滑动窗口小结 (一)-爱代码爱编程

目录 小结以及代码框架76. 最小覆盖子串滑动窗口代码以及注释567. 字符串的排列滑动窗口438. 找到字符串中所有字母异位词3. 无重复字符的最长子串化简框架reference 小结以及代码框架 滑动窗口技巧属于双指针技巧。 该算法的思路为维护一个窗口,不断滑动,然后更新答案。 大致框架如下:[参考labuladong的

LeetCode 300. 最长连续序列(map + 朴素遍历)+(set + 优化遍历)—— JavaScript-爱代码爱编程

相似题:LeetCode 300. 最长上升子序列 本题链接:https://leetcode-cn.com/problems/longest-consecutive-sequence/ 题描述: 解题思路(map + 遍历): 利用 map 表示当前元素是否存在数组中。 每次对当前元素进行向前和向后的遍历,统计该元素的连续序列的长度。 代

C++显示杨辉三角-爱代码爱编程

利用循环队列的数据结构: //"CirQueue.h" #include<iostream> using namespace std; template<class T> class CirQueue { private: T *base; int front; int rear; int queuesize

解 poj1502-MPI Maelstrom(单源最短路径的广搜与dijkstra实现)-爱代码爱编程

文章目录 Description题意解析1.队列式分支限界法广搜2.优先队列式分支限界法广搜3.Dijkstra算法 Description BIT has recently taken delivery of their new supercomputer, a 32 processor Apollo Odyssey distribu

线程安全的队列-ArrayBlockingQueue源码分析-爱代码爱编程

一,ArrayBlockingQueue源码分析 ArrayBlockingQueue是队列的一种,队列的特点嘛,先出先出,然而这种队列是一种线程安全阻塞式的队列,为什么是阻塞式队列?我想,这正好是我写和分析这篇文章的内容所在。 由于本篇内容涉及的内容比较多,所以有些地方自己不会特地讲的很详细,但是足够自己使自己明白了,一般文章出来的时候,如果连

队列的顺序存储-爱代码爱编程

用循环数组来,描述一个队列。 要搞清楚两件事: 何时为空何时为满头文件 #ifndef _HEAD_H #define _HEAD_H #define MINSIZE 5 typedef int ElementType; typedef struct node* Queue; typedef struct node{ Elemen

JZ59-按之字形顺序打印二叉树-爱代码爱编程

【题目描述】 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。 示例 输入输出{8,6,10,5,7,9,11}[[8],[10,6],[5,7,9,11]]【队列】 /* struct TreeNode { int val; struc