ACM 选手图解 LeetCode 对称二叉树-阿里云开发者社区

大家好呀，我是对称蛋。

今天解决对称二叉树，比较有意思的经典题目，检查二叉树是否是镜像对称。

不比比，直接开搞。

LeetCode 101：对称二叉树

题意

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

示例

二叉树 [1,2,2,3,4,4,3] 镜像对称。

二叉树 [1,2,3,null,3,null,3] 非镜像对称

提示

爱帅蛋
么么哒

题目解析

题目经典，难度简单。

这道题又是说对称，又是说镜像的，看着挺唬人，其实就是看左右子树是否相互翻转。

再直白点就是比较两棵树（在这道题里，根节点没什么用，把根节点拿掉来看，就是两棵树）。

那怎么比较呢？

我来把图的颜色稍作修改，来看下图：

是不是就很一目了然？

左子树的左节点和右子树的右节点，左子树的右节点和右子树的左节点比较即可。

如果一棵树的左子树的左子树和右子树的右子树相等，左子树的右子树和右子树的左子树相等，那这棵树就是对称的。

递归法

还是老套路，根据【递归算法】文章中讲的，实现递归，需要两步：

找出重复的子问题（递推公式）。
终止条件。

(1) 找出重复的子问题。

这个在上面看图的时候其实已经找出来了。

对于每一层来说，比较的都是左子树的左节点和右子树的右节点，左子树的右节点和右子树的左节点是否相等。

如果相等就返回 true，不相等就返回 false。

# 使用递归，对接下来的每一层做判断
# 判断左子树的左子树和右子树的右子树是否相等
leftrightTree = self.compareTree(left.left, right.right)
# 判断左子树的右子树和右子树的左子树是否相等
rightleftTree = self.compareTree(left.right, right.left)
isCompareTree = leftrightTree and rightleftTree

(2) 确定终止条件。

对称二叉树这道题因为比较的是节点的值是否相同，所以涉及的情况有点多。

首先是节点为空的情况，这种必须首先考虑，不然会出现空指针的比较。

节点为空，分为 3 种情况：

左右节点都为空，此时相当于只有个头节点，是对称的。
左节点为空，右节点不为空，显然不对称。
左节点不为空，右节点为空，显然也是不对称的。

节点为空的情况判断完了，剩下就是节点不为空的情况，节点不为空，其实终止就 1 种情况：

比较两个节点的值，如果不相等，则不对称。

# 若左右节点不存在（即只有根节点）
if left == None and right == None:
    return True
# 左节点为空右节点不为空或左节点不为空右节点为空，则不对称
elif (left == None and right != None) or (left != None and right == None):
    return False
# 左右节点不为空，但数值不等，则不对称
elif left.val != right.val:
    return False

递归二步曲确定完了，这道题其实也就做出来了。

Python 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def compareTree(self, left, right):
        # 若左右节点不存在（即只有根节点）
        if left == None and right == None:
            return True
        # 左节点为空右节点不为空或左节点不为空右节点为空，则不对称
        elif (left == None and right != None) or (left != None and right == None):
            return False
        # 左右节点不为空，但数值不等，则不对称
        elif left.val != right.val:
            return False
        # 使用递归，对接下来的每一层做判断
        # 判断左子树的左子树和右子树的右子树是否相等
        leftrightTree = self.compareTree(left.left, right.right)
        # 判断左子树的右子树和右子树的左子树是否相等
        rightleftTree = self.compareTree(left.right, right.left)
        isCompareTree = leftrightTree and rightleftTree 
        return isCompareTree
    def isSymmetric(self, root: TreeNode) -> bool:
        # 空树
        if root == None:
            return True
        return self.compareTree(root.left, root.right)

Java 代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public boolean isSymmetric(TreeNode root) {
    if(root == null) {
      return true;
    }
    return compareTree(root.left,root.right);
  }
  boolean compareTree(TreeNode left, TreeNode right) {
        // 若左右节点不存在（即只有根节点）
    if(left == null && right == null) {
      return true;
    }
        // 左节点为空右节点不为空或左节点不为空右节点为空，则不对称
    if((left == null && right != null) || (left != null && right == null)) {
      return false;
    }
        // 左右节点不为空，但数值不等，则不对称
    if(left.val!=right.val) {
      return false;
    }
        // 判断左子树的左子树和右子树的右子树是否相等
        boolean leftrightTree = compareTree(left.left,right.right);
        // 判断左子树的右子树和右子树的左子树是否相等
        boolean rightleftTree = compareTree(left.right,right.left);
        boolean isCompareTree = leftrightTree && rightleftTree;
        return isCompareTree;
  }
}

此解法，由于每个节点被遍历一次，所以时间复杂度为 O(n)。

使用递归，在过程中额外调用了栈空间，所以空间复杂度为 O(n)。

非递归法（迭代）

在递归法法中我说过：对于每一层来说，比较的都是左子树的左节点和右子树的右节点，左子树的右节点和右子树的左节点是否相等。

其实这有点类似层次遍历。

每次将当前层的节点，按照左子树的左节点、右子树的右节点、左子树的右节点和右子树的左节点放入队列，再依次两两出队列，比较数值是否相等。

比如对于下图：

首先初始化队列，并将根节点的左右节点入队列。

# 初始化队列
queue = [root.left, root.right]

当队列不为空，将前两个元素出队列进行比较。

# 从队列中取出两个节点
left = queue.pop(0)
right = queue.pop(0)
# 若两个节点都为空（左右节点不存在），则继续循环
if left == None and right == None:
    continue
# 左节点为空右节点不为空或左节点不为空右节点为空，则不对称
elif (left == None and right != None) or (left != None and right == None):
    return False
# 左右节点不为空，但数值不等，则不对称
elif left.val != right.val:
    return False

下面再依次将左子树的左节点、右子树的右节点、左子树的右节点和右子树的左节点放入队列。

接下来还是按照上面的方式出队列、比较、入队列...直至队列为空。

Python 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None:
            return True
        # 初始化队列
        queue = [root.left, root.right]
        while queue:
            # 从队列中取出两个节点
            left = queue.pop(0)
            right = queue.pop(0)
            # 若两个节点都为空（左右节点不存在），则继续循环
            if left == None and right == None:
                continue
            # 左节点为空右节点不为空或左节点不为空右节点为空，则不对称
            elif (left == None and right != None) or (left != None and right == None):
                return False
            # 左右节点不为空，但数值不等，则不对称
            elif left.val != right.val:
                return False
            # 左节点的左孩子和右节点的右孩子入队列
            queue.append(left.left)
            queue.append(right.right)
            # 左节点的右孩子和右节点的左孩子入队列
            queue.append(left.right)
            queue.append(right.left)
        return True

Java 代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public boolean isSymmetric(TreeNode root) {
    if(root==null) {
      return true;
    }
    // 初始化队列
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root.left);
    queue.add(root.right);
    while(queue.size() > 0) {
      // 从队列中取出两个节点
      TreeNode left = queue.removeFirst();
      TreeNode right = queue.removeFirst();
      // 若两个节点都为空（左右节点不存在），则继续循环
      if(left == null && right == null) {
        continue;
      }
            // 左节点为空右节点不为空或左节点不为空右节点为空，则不对称
      if((left == null && right != null) || (left != null && right == null)){
        return false;
      }
            // 左右节点不为空，但数值不等，则不对称
      if(left.val != right.val) {
        return false;
      }
      // 左节点的左孩子和右节点的右孩子入队列
      queue.add(left.left);
      queue.add(right.right);
      // 左节点的右孩子和右节点的左孩子入队列
      queue.add(left.right);
      queue.add(right.left);
    }
    return true;
  }
}

同样，非递归法，时间复杂度为 O(n)，空间复杂度为 O(n)。

图解对称二叉树到这就结束辣，大噶伙儿学废了嘛？

是不是感觉还挺简单的，我一直觉得，二叉树的题目还蛮有意思的。

一道题，拆着拆着就拆成了自己认识的样子。

二叉树这个专题，我会带大家多做一些实战题，争取学完就搞懂。

大家加油，当然也要记得给本蛋点赞 + 在看 + 转发，给我加加油！

我是帅蛋，我们下次见辣！

ACM 选手图解 LeetCode 对称二叉树

热门文章

最新文章

相关电子书