101. 对称二叉树

[luryZhu]

101. 对称二叉树
     给定一个二叉树，检查它是否是镜像对称的。
     https://leetcode-cn.com/problems/symmetric-tree/

思路1：DFS递归
检查树是否对称：检查左右子树是否对称
递归函数输入参数：左子树右子树
左子树右子树皆空（叶子结点），返回true
左右子树其一为空，返回false
左右子树都非空：

• 值不等返回false
• 值相等，判断左.左==右.右 && 左.右==右.左

代码

var isSymmetric = function(root) {
    if (!root) return true
    let dfs=(l,r)=>{
        if (!l && !r) return true
        if (!l) return false
        if (!r) return false
        if (l.val !== r.val) return false
        return (dfs(l.left,r.right)&&dfs(l.right,r.left))
    }
    return dfs(root.left,root.right)
};

思路2：队列迭代
队列
判断树是否对称：判断两个子树是否对称
每次从队列取出两个结点判断是否对称
根节点的左右孩子入队
队列非空时：

• 前两个元素出队
• 判断这两个元素是否对称：
  • 皆空 continue
  • 其一为空，返回false
  • 都非空，但值不等，返回false
  • 都非空，值等，左.左，右.右 ，左.右，右.左 入队

代码

var isSymmetric = function(root) {
    if (!root) return true
    let queue=[root.left,root.right]
    while(queue.length){
        let l=queue.shift()
        let r=queue.shift()
        if (!l && !r) continue
        if (!l) return false
        if (!r) return false
        if (l.val!==r.val) return false
        queue.push(l.left,r.right,l.right,r.left)
    }
    return true
};