判断两棵二叉树是否完全相同。
输入空间：二叉
解空间：二叉
解题“七步走” (保持这种sense)：
- 题意 Scenario
- 假设 Assumptions
- 举例与输入输出 Examples and figure out Input/Output
- 思路（什么数据结构， 什么算法）Thinking Process (What data structure, algorithm?)
- 代码 Coding
- 复杂度分析 Complexity Analysis
- 测试 Tests
题目要求
原题链接
判断两棵二叉树是否完全相同。
假设
面试者：如果两棵二叉树都是空树（即一个节点都没有），那么它们算相同吗？
面试官：你说的正是最根本的情况，这是算的。
举例与输入输出
例子直接用LeetCode上的图。
思路：分治法
由于这道题与LC 101判断对称树很接近。
用分治法解决即可。主要核心点在于base cases（递归的基本情况的判断），而同时又基于我先前写过的这篇由热心读者提供的LC 101的优化解法，LC 100这道题的基本情况判断可以分为如下两方面:
- 当被比较的两个节点，当中有一个可能为空节点的时候，我们应该返回什么？
- 在不为第1点的基础上，如果被比较的两个节点的数值不等的情况下，我们返回什么？
很显然，base case可能返回true的情况，已经在第1点中被覆盖了。那么，最后的问题也就容易了，分治法，处理分和治的过程嘛。由于此题分与治的过程简单，所以可以写在一行代码当中搞定。
本题（LC 100）代码
/**
* 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 p == q;
}
else if (p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
时间空间复杂度
时间复杂度：由于要遍历二叉树的所有节点，所以O(n)，
空间复杂度：为递归栈的深度，所以是O(log(n))。