解法一 递归

从根结点开始，首先判断两棵树根节点是否为null，再判断是否相等，然后再对左子树与右子树进行相同的操作。

/** * 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) { if(p==null && q == null) return true; if(p == null | q ==null) return false; if(p.val != q.val) return false; else return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } }

解法二 迭代

使用两个双端队列，从根节点开始每次迭代弹出两个对应的节点， 用check方法判断两个节点p、q是否满足:

p、q不为nullp.val = q.val

如果满足则继续压入子节点

/** * 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) { if(p == null && q == null) return true; if(!check(p,q)) return false; ArrayDeque<TreeNode> deqP = new ArrayDeque<>(); ArrayDeque<TreeNode> deqQ = new ArrayDeque<>(); deqP.addLast(p); deqQ.addLast(q); while(!deqP.isEmpty()){ p = deqP.removeFirst(); q = deqQ.removeFirst(); if(!check(p,q)) return false; if(p!=null){ if(!check(p.left,q.left)) return false; if(p.left != null){//check返回true有两种情况，确保p.left 与 q.left 不为null deqP.addLast(p.left); deqQ.addLast(q.left); } if(!check(p.right,q.right)) return false; if(p.right != null){ deqP.addLast(p.right); deqQ.addLast(q.right); } } } return true; } //检查pq节点是否相等 public boolean check(TreeNode p, TreeNode q){ if(q == null && p == null) return true; if(q == null || p == null) return false; if(p.val != q.val) return false; return true; } }