leetcode top100挑战, 每天不鸽一道题之对称二叉树(12/100)-一一网

这是我参与更文挑战的第21天，活动详情查看：更文挑战

题目描述

对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

leetcode-cn.com/problems/sy…

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3
复制代码

解题分析

1. 递归

直接上讲解。

这道题递归轻松解决。
首先我们确定如何成立对称。

    1
   / \
  2   2
 / \ / \
3  4 4  3


1. left.val 和right.val相等
2. 左右子节点存在并且值相等
3. 最后子节点为null

我们直接递归就行。

如上图，1为树顶，不用去管。

然后需要判断树顶下的左右节点是否存在，
1. 如果左右节点相等，说明两个节点都不存在，这样也是对称的可以直接返回true，因为子节点也不存在，就一个树顶。
2. 如果左右节点有一个值不存在也就是等于0，那就直接返回false就行，因为他们不对称，下面子节点也不用去看了。
3. 最后一个判断条件，如果左右节点两个节点的值相等且存在，则递归节点下的子节点判断上述三个条件。
4. 得出最后结果是否为对称。我们直接看代码。
复制代码

来人上代码！！！！！

/**
 * 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)
 *     }
 * }
 */
 // 用于递归的helper函数，接收参数为左节点和右节点。
const helper = (left: TreeNode | null, right: TreeNode | null) => {
    // 如果传入的左节点和右节点都不存在 也是镜像
    if(left == right) return true 
    // 如果左节点和右节点有一个的值不存在，那就不是对称的两个节点
    else if (left.val === 0 || right.val === 0) return false 
    // 最后判断并递归，左节点和右节点都存在并且值为相等，那就递归他们的子节点。
    return (left.val === right.val) && (helper(left.left, right.right)) && (helper(left.right, right.left))
}
function isSymmetric(root: TreeNode | null): boolean {
    //传入的root可能为null，做下判断。
    if(root === null || root === undefined) return true 
    else {
        
        return helper(root.left, root.right)
    }
};

复制代码