【Description】
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Example 1:
Input: 1 1
/ \ / 2 3 2 3
[1,2,3], [1,2,3]
Output: true
Example 2:
Input: 1 1
/ 2 2
[1,2], [1,null,2]
Output: false
Example 3:
Input: 1 1
/ \ / 2 1 1 2
[1,2,1], [1,1,2]
Output: false
【AC code】
Reference: https://leetcode.com/articles/same-tree/
一、递归 时间复杂度：O(n)
1 class Solution { 2 public boolean isSameTree(TreeNode p, TreeNode q) { 3 if (p == null && q == null) return true; 4 if ((p != null && q == null) || (p == null && q != null) || p.val != q.val) return false; 5 return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); 6 } 7 }
二、迭代 时间复杂度：O(n)
1 class Solution { 2 public boolean isSameTree(TreeNode p, TreeNode q) { 3 Queue<TreeNode> queue = new LinkedList<>(); 4 queue.offer(p); 5 queue.offer(q); 6 while (!queue.isEmpty()) { 7 TreeNode first = queue.poll(); 8 TreeNode second = queue.poll(); 9 if (first == null && second == null) continue; 10 if ((first == null || second == null) || first.val != second.val) return false; 11 queue.offer(first.left); 12 queue.offer(second.left); 13 queue.offer(first.right); 14 queue.offer(second.right); 15 } 16 return true; 17 } 18 }
【拓展知识】
Reference: https://blog.csdn.net/u012050154/article/details/60572567
在第二种方法中队列的入队和出队分别采用了offer()和poll()，而不是add()和remove()，这是为了便于程序有效判断。
原文：https://www.cnblogs.com/moongazer/p/11536142.html
