LeetCode 100. Same Tree
解法一 Recursion
思路
两树相同,则比较的两个节点中不能有其中一个为 null,节点的值需要相等,两个节点的左子树和右子树也要相等。
代码
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (q == null && p == null) return true;
if (q == null || p == null) return false;
if (q.val != p.val) return false;
return isSameTree(q.left, p.left) && isSameTree(q.right, p.right);
}
}
复杂度分析
- 时间复杂度
- 遍历一遍二叉树,花费 O(n) 时间
- 空间复杂度
- O(n) – Skewed Tree
- O(logn) – Balanced Tree
解法二 Iteration
思路
和递归思路相同,就是使用了 queue 储存两个树将要比较的节点。(用 stack 也可以)
代码
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(p);
queue.offer(q);
while (!queue.isEmpty()) {
TreeNode ptree = queue.poll();
TreeNode qtree = queue.poll();
if (ptree == null && qtree == null) continue; // 当两树都是空树时,继续循环
else if (ptree == null || qtree == null) return false;
else if (ptree.val != qtree.val) return fasle;
else {
queue.offer(p.left);
queue.offer(q.left);
queue.offer(p.right);
queue.offer(q.right);
}
}
return true;
}
}
复杂度分析
- 时间复杂度
- O(N)
- 空间复杂度
- O(N) Keep the queue
Takeaway
第101题 symmetric tree 思路相同,p,q树都是 root,然后左子树和右子树比,右子树和左子树比。recursion时需要满足根节点相等且左右对称。
本作品采用《CC 协议》,转载必须注明作者和本文链接