Frontend Interview

Appearance

101. 对称二叉树 ​

题目链接：https://leetcode.cn/problems/symmetric-tree/

代码 ​

ts
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isSymmetric(root: TreeNode | null): boolean {
    if (root === null) return true;
    return symmetric(root, root);
};

function symmetric(left: TreeNode | null, right: TreeNode | null): boolean {
    if (!left && !right) return true;
    if (!left || !right) return false;

    if (left.val === right.val) {
        return symmetric(left.left, right.right) && symmetric(left.right, right.left);
    }
    else return false
};

思路 ​

判断一棵二叉树是否对称，需要比较左右子树是否镜像对称：

  1. 递归终止条件：
    • 如果左右节点都为空，返回 true
    • 如果左右节点只有一个为空，返回 false
  2. 递归比较：
    • 比较左右节点的值是否相等
    • 递归比较左子树的左孩子和右子树的右孩子
    • 递归比较左子树的右孩子和右子树的左孩子

关键点 ​

  • 对称比较：左子树的左孩子 vs 右子树的右孩子，左子树的右孩子 vs 右子树的左孩子

  • 使用辅助函数 symmetric 进行递归比较

  • 需要同时满足值相等和子树对称

  • 时间复杂度 O(n)，其中 n 是节点数量

  • 空间复杂度 O(h)，其中 h 是树的高度，递归调用栈的深度