欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

100相同的树

程序员文章站 2022-05-20 19:24:47
...

题目描述

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

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

思路分析

  • 思路一:看到用例,就想到最麻烦的做法。先把两个树用层次遍历存储为数组,数组进行比较。
  • 思路二:递归。首先判断 p、q为空的情况,然后判断它们的值是否相等。若以上判断通过,则递归对子结点做同样操作。

代码实现

 /**
     * 递归解法
     * @param p
     * @param q
     * @return
     */
    public static boolean isSameTree1(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree1(p.left, q.left) && isSameTree1(p.right, q.right);
    }

    /**
     * 层次遍历解法
     * @param p
     * @param q
     * @return
     */
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        ArrayList<Integer> arrayList1 = levelOrder(p);
        ArrayList<Integer> arrayList2 = levelOrder(q);

        if (arrayList1.size() != arrayList2.size()) {
            return false;
        }
        int i = 0;
        while (i < arrayList1.size() && i < arrayList2.size()) {
            if (!arrayList1.get(i).equals(arrayList2.get(i))) {
                return false;
            }
            i++;
        }

        return true;
    }

    public static ArrayList<Integer> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> arrayList = new ArrayList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode tmp = queue.poll();
                if (tmp == null) {
                    arrayList.add(0);
                    continue;
                }
                arrayList.add(tmp.val);
                queue.offer(tmp.left);
                queue.offer(tmp.right);
            }
        }
        return arrayList;
    }

相关标签: leetcodeBinaryTree