剑指 Offer 28.对称的二叉树
解题思路：
-
终止条件：
- 当 L 和 R 同时越过叶节点： 此树从顶至底的节点都对称，因此返回 true；
- 当 L 或 R 中只有一个越过叶节点： 此树不对称，因此返回 false；
- 当节点 L 值 != 节点 R 值： 此树不对称，因此返回 false；
-
递推工作：
- 判断两节点 L.left 和 R.right 是否对称，即 recur(L.left, R.right) ；
- 判断两节点 L.right 和 R.left 是否对称，即 recur(L.right, R.left) ；
-
返回值： 两对节点都对称时，才是对称树，因此用与逻辑符 && 连接；
图解：
复杂度：
-
时间复杂度：O(N)；
-
空间复杂度：O(N)；
代码实现：
function isSymmetric(root: TreeNode | null): boolean {
if (root === null) {
return true;
}
function reverse(left, right) {
if (left === null && right === null) {
return true;
}
if (left === null || right === null || left.val !== right.val) {
return false;
}
return reverse(left.left, right.right) && reverse(left.right, right.left)
}
return reverse(root.left, root.right);
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
第 3️⃣ 座大山：Web API
上一篇
评论
