Go 刷 leetcode｜树系列之对称二叉树

今天为大家讲解 LeetCode 第 101 题，是一道关于二叉树的题目。

题目描述

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

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

进阶：

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/symmetric-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

关于「树」的题目，大多使用「递归」思想来解决。这道题的解题思路如下：

1.怎么判断一棵树是不是对称二叉树？答案：如果所给根节点，为空，那么是对称。如果不为空的话，当他的左子树与右子树对称时，他对称

2.那么怎么知道左子树与右子树对不对称呢？在这我直接叫为左树和右树 答案：在左树和右树均不为空情况下，如果左树的左孩子与右树的右孩子对称，左树的右孩子与右树的左孩子对称，那么这个左树和右树就对称。

仔细读这句话，是不是有点绕？怎么感觉有一个功能A我想实现，但我去实现A的时候又要用到A实现后的功能呢？

当你思考到这里的时候，递归点已经出现了：递归点：我在尝试判断左树与右树对称的条件时，发现其跟两树的孩子的对称情况有关系。

想到这里，你不必有太多疑问，上手去按思路写代码，函数A（左树，右树）功能是返回是否对称

定义 函数A（左树，右树），函数处理的逻辑如下：

先处理判断：如果左树和右树均为空，肯定对称返回真；

如果左树和右树只有一个为空，肯定不对称返回假；

其他情况，判断：左树节点值等于右树节点值 且 函数A（左树的左子树，右树的右子树），函数A（左树的右子树，右树的左子树）均为真 才返回真

代码实现

//go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return partSym(root.Left, root.Right)
}

func partSym(left, right *TreeNode) bool {
    // 注意以下两个if判断顺序不能反
    // 都为nil
    if left == nil && right == nil {
        return true
    }
    // 只有一个为nil
    if left == nil || right == nil {
        return false
    }
    if ((left.Val == right.Val) && partSym(left.Left, right.Right) && partSym(left.Right, right.Left)) {
        return true
    }
    return false
}

//java
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return partSym(root.left, root.right);
    }

    private boolean partSym(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null || node2 == null || node1.val != node2.val) {
            return false;
        }
        return partSym(node1.left, node2.right) && partSym(node1.right, node2.left);
    }
}

郑重声明：

所展示代码已通过 LeetCode 运行通过，请放心食用～