对称二叉树

题目描述

给你一个二叉树的根节点 root，检查它是否轴对称。

示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false

思路&js代码

1、递归

const check = (p: TreeNode | null, q: TreeNode | null): boolean => {
    if (!p && !q) return true;
    if (!p || !q) return false;
    return p.val === q.val && check(p.left, q.right) && check(p.right, q.left);
}
var isSymmetric = function(root: TreeNode | null): boolean {
    return check(root.left, root.right);
};
 

2、迭代

const check = (u: TreeNode | null, v: TreeNode | null): boolean => {
    const q: (TreeNode | null)[] = [];
    q.push(u),q.push(v);
 
    while (q.length) {
        u = q.shift()!;
        v = q.shift()!;
 
        if (!u && !v) continue;
        if ((!u || !v) || (u.val !== v.val)) return false;
 
        q.push(u.left); 
        q.push(v.right);
 
        q.push(u.right); 
        q.push(v.left);
    }
    return true;
}
var isSymmetric = function(root: TreeNode | null): boolean {
    return check(root, root);
};