100相同的树

题目描述

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

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

思路分析

• 思路一：看到用例，就想到最麻烦的做法。先把两个树用层次遍历存储为数组，数组进行比较。
• 思路二：递归。首先判断 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;
    }