1. 首页
  2. LeetCode

每日一道 LeetCode (20):相同的树

每日一道 LeetCode (20):相同的树

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:相同的树

题目来源:https://leetcode-cn.com/problems/same-tree/

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

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

示例 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

解题思路

今天又见到新的数据结构了,这次遇到的是树,或者简单的说是二叉树。

例行惯例,第一次的见的数据结构基本上都没啥想法,直接看答案。

只能怨自己肚子里墨水太少,不会的太多,搞不定的只能答案走起,算法这玩意,答案背多了再遇到题也就有想法了。

先放一段树的结构代码:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode() {}
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

这段代码很简单,树上的值是 int 类型,然后有一个左节点有一个右节点。

树结构介绍完毕,接下来梳理两种遍历树的方案,或者说是常规操作。

解题的话提供两种方案,一种是递归,一种是循环。

递归

首先极限值判断,两个二叉树都为空肯定相等,如果一个为空另一个不为空肯定不相等。

接下来如果两个二叉树都不为空,那么首先判断它们的根节点的值是否相同,若不相同则两个二叉树一定不同,若相同,再分别判断两个二叉树的左子树是否相同以及右子树是否相同,然后接着递归这个过程。

循环

首先和上面一样,先进行极限值判断。

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

  • 比较两个节点的值,如果两个节点的值不相同则两个二叉树一定不同。
  • 如果两个节点的值相同,则判断两个节点的子节点是否为空,如果只有一个节点的左子节点为空,或者只有一个节点的右子节点为空,则两个二叉树的结构不同,因此两个二叉树一定不同。
  • 如果两个节点的子节点的结构相同,则将两个节点的非空子节点分别加入两个队列,子节点加入队列时需要注意顺序,如果左右子节点都不为空,则先加入左子节点,后加入右子节点。

结果,如果循环结束的时候两个队列同时为空,那么这两个二叉树相同,如果有一个不为空,那肯定不相同。

代码:

// 迭代
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);
    }
}

// 循环
public boolean isSameTree_1(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;

    Queue<TreeNode> queue1 = new LinkedList<>();
    Queue<TreeNode> queue2 = new LinkedList<>();
    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 BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code