*题目描述:
解题思路:
- 深度优先搜索:同时遍历这两颗树,比对节点值是否一致,然后比对其左右节点是否相同
- 广度优先搜索:也是同时遍历,使用两个队列存储入队的节点,及时返回错误情况,最后跳出循环时,一定要注意,可能两棵树本身节点数量并不相同。
代码:
//深度优先搜索: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ 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; } return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } }
//广度优先搜索: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ 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; // } Queue<TreeNode> queue1 = new LinkedList<>(); Queue<TreeNode> queue2 = new LinkedList<>(); queue1.offer(p); queue2.offer(q); while (!queue1.isEmpty() && !queue2.isEmpty()) { TreeNode tmp1 = queue1.poll(); TreeNode tmp2 = queue2.poll(); if (tmp1.val != tmp2.val) { return false; } TreeNode left1 = tmp1.left; TreeNode left2 = tmp2.left; TreeNode right2 = tmp2.right; TreeNode right1 = tmp1.right; if (left1 == null ^ left2 == null) { return false; } if (right1 == null ^ right2 == null) { return false; } if (left1 != null) { queue1.offer(left1); } if (left2 != null) { queue2.offer(left2); } if (right1 != null) { queue1.offer(right1); } if (right2 != null) { queue2.offer(right2); } } return queue1.isEmpty() && queue2.isEmpty(); } }