解题步骤
- 分:获取两个树的左子树和右子树
- 解:递归地判断两个树的左子树是否相同,右子树是否相同
- 合:将上述结果合并,如果根节点的值相同,树就相同
通过分而治之思想实现
- 时间复杂度:O (n)
空间复杂度:O (h)
function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q) return false;
if (p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)) {
return true;
}
return false;
}
代码中利用递归遍历了树的所有节点,所以时间复杂度是 O (n) ,而空间复杂度是 O (h) h 是树的高度,因为存在调用堆栈占据了空间。