20.相同的树-LeetCode-Java

给定两个二叉树，编写一个函数来检验它们是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 示例 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 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ /** * 方法一：先序遍历两颗二叉树 判断是否相同(分治思想) */ class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { return preOrder(p, q); } private boolean preOrder(TreeNode p, TreeNode q) { if (p != null && q != null) { if (p.val != q.val) return false; return preOrder(p.left, q.left) && preOrder(p.right, q.right); } else if (p == null && q == null) return true; else return false; } } /** * 方法二：层次遍历两颗二叉树 判断是否相同(层次遍历需要使用队列) */ class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { return levelOrder(p, q); } Queue queueP = new LinkedList(); // 队列 Queue queueQ = new LinkedList(); private boolean levelOrder(TreeNode p, TreeNode q) { queueP.add(p); queueQ.add(q); while (!queueP.isEmpty() && !queueQ.isEmpty()) { TreeNode nodeP = (TreeNode) queueP.poll(); // 返回队列第一个元素 并出队列 TreeNode nodeQ = (TreeNode) queueQ.poll(); if (nodeP != null && nodeQ != null) { if (nodeP.val != nodeQ.val) return false; // 比较出队列的两个值是否相等 queueP.add(nodeP.left); queueP.add(nodeP.right); queueQ.add(nodeQ.left); queueQ.add(nodeQ.right); } else if (nodeP == null && nodeQ != null) return false; else if (nodeP != null && nodeQ == null) return false; } return true; } }