【LeetCode 101】对称二叉树

约定不等于承诺〃 2022-11-29 03:10 119阅读 0赞

#### 题目描述 ####

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

例如，二叉树 \[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

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

#### 解题思路 ####

**递归：**

递归的思路比较简单，具体实现思路如下：

*  首先判断当前树是否为空，空则直接返回true，否则就左子树的左子树和右子树的右子树是否相等
 *  如果左节点或者右节点为空时，就比较对应的右节点或左节点是否为空，为空则返回true，否则就返回false
 *  如果左右节点都不为空，就判断左节点的左节点和右节点的右节点是否相等
 *  如果相等，就传入该节点的子节点进行递归，否则就返回false

递归的时间复杂度为O(n)，空间复杂度为O(n)。

**迭代：**

迭代方法需要借助队列来实现。

迭代的时间复杂度为O(n)，空间复杂度为O(n)。

#### 代码实现 ####

**递归：**

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
    /** * @param {TreeNode} root * @return {boolean} */
    var isSymmetric = function(root) { 
        if(!root){ 
            return true
        }
        return isSameTree(root.left, root.right)
    };
    
    const isSameTree = (l, r) => { 
        if(!l) return r === null
        if(!r) return l === null
    
        if(l.val !== r.val) return false
        return isSameTree(l.left, r.right,) && isSameTree(l.right, r.left)
    }

**迭代：**

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
    /** * @param {TreeNode} root * @return {boolean} */
    const isSymmetric = (root) => { 
      if (!root) return true
      let queue = [root.left, root.right]
      while (queue.length > 0) { 
        let t1 = queue.shift(), t2 = queue.shift()
        if (t1 === null && t2 === null) continue
        if (t1 === null || t2 === null || t1.val !== t2.val) return false
        queue.push(t1.left, t2.right, t1.right, t2.left)
      }
      return true
    }

#### 提交结果 ####

**递归：**  
![在这里插入图片描述][20200819011523807.png]  
**迭代：**

![在这里插入图片描述][20200819014818888.png]

[20200819011523807.png]: /images/20221124/fc72c4aeaf0c464c9510b7ddb29245fc.png?
[20200819014818888.png]: /images/20221124/f1710762780e4d25b98dd7b2aa7337f0.png?