专栏首页前端小书童一天一大 lee(相同的树)难度:简单-Day20200807

一天一大 lee(相同的树)难度:简单-Day20200807

题目:

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

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

示例

  1. 示例 1
输入:       1         1
          / \       / \
         2   3     2   3

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

输出: true
  1. 示例 2
输入:      1          1
          /           \
         2             2

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

输出: false
  1. 示例 3
输入:       1         1
          / \       / \
         2   1     1   2

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

输出: false

抛砖引玉

抛砖引玉

递归逐个校验

  • 递归传入节点判断是否相同,相同则继续校验左右节点
  • 同时递归到最终节点及 null 则说明所有校验均通过返回 true
  • 两个树不是同时遇到最终节点 返回 false
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
  // 判断到最终节点相同 返回true
  if (p === null && q === null) return true
  // 两个树不是同时遇到最终节点 返回false
  if (p === null || q === null) return false
  // 传入节点是否相同
  if (p.val !== q.val) return false
  // 递归判断每个节点的左右节点
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}

广度优先搜索

  • 为每个树声明一个数组存放元素
  • 相同则从数组中取出
  • 不同则返回 false
var isSameTree = function (p, q) {
  // 判断到最终节点相同 返回true
  if (p === null && q === null) return true
  // 两个树不是同时遇到最终节点 返回false
  if (p === null || q === null) return false

  let dp1 = [p],
    dp2 = [q]

  while (dp1.length && dp2.length) {
    let node1 = dp1.shift(),
      node2 = dp2.shift()
    if (node1.val != node2.val) {
      return false
    }
    let left1 = node1.left,
      right1 = node1.right,
      left2 = node2.left,
      right2 = node2.right
    // 异或,均为false或者均为true 结果为false,不然为true
    if ((left1 === null) ^ (left2 === null)) return false
    if ((right1 === null) ^ (right2 === null)) return false
    // 该节点相同,继续推送下一个节点进行比较
    if (left1 !== null) dp1.push(left1)
    if (right1 !== null) dp1.push(right1)
    if (left2 !== null) dp2.push(left2)
    if (right2 !== null) dp2.push(right2)
  }
  // 所有节点比较完成返回true
  return dp1.length === 0 && dp2.length === 0
}

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:坑人的小书童

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【一天一大 lee】单词规律 II (难度:困难) - Day20201217

    给你一种规律 pattern 和一个字符串 str,请你判断 str 是否遵循其相同的规律。

    前端小书童
  • 【一天一大 lee】N皇后 II (难度:困难) - Day20201017

    n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

    前端小书童
  • 【一天一大 lee】将数组拆分成斐波那契序列 (难度:中等) - Day20201208

    给定一个数字字符串 S,比如 S = "123456579",我们可以将它分成斐波那契式的序列 [123, 456, 579]。

    前端小书童
  • 什么?字符串为空?

    当字符串为null,undefined,NaN,0,false,""这几个时,if(value)的结果都为false,if(!value)包含了我们常见的空值情...

    说故事的五公子
  • java容器考点总结和源码剖析!!!

    容器主要包括 Collection 和 Map 两种,Collection 存储着对象的集合,而 Map 存储着键值对(两个对象)的映射表。

    用户5224393
  • BATJ面试必会之 Java 容器篇

    容器主要包括 Collection 和 Map 两种,Collection 存储着对象的集合,而 Map 存储着键值对(两个对象)的映射表。

    乔戈里
  • 透过源码学习设计模式2—Spring ProxyFactory和代理模式

    代理就像我们生活中的房产中介,你不直接与房主,银行接触,而是通过中介与他们沟通联系。 代理的结构如图所示:

    java达人
  • python3–python模块+(复习)

    老七Linux
  • java.util.ConcurrentModificationException原因

    我们要写个遍历Map集合,删除指定key值的方法,我们估计会这样写。 刚开始我习惯上会写上map.remove(entry.getKey()),remove...

    SmileNicky
  • Python基础知识

    print 打印语句 # 注释语句 print语句中带有变量可以把变量和字符串使用,隔开或者使用+进行连接 逗号会用空格分开两个变量,+会把两个变量作为一...

    苦咖啡

扫码关注云+社区

领取腾讯云代金券