[数据结构与算法]力扣打卡：101. 对称二叉树 - 递归 明确一个递归函数的定义

力扣打卡：101. 对称二叉树

解题思路

从顶开始，检查左右两个节点是否相同，然后检查左节点的左孩子和右节点的右孩子 以及 左节点的右孩子和右节点的左孩子，就能很大程度上避免写条件的麻烦，因为每次检测都是在对比上层是否堆成

• 对于一个节点（二叉树），只需要判断其值和左右孩子是否对称，如果不对称，那么无需继续判断。如果对称，则判断另外三个父子节点了。

• 写递归函数，一定要明确这个函数的意义是什么，即使刚开始不知道怎么如何开始，只需要按照定义去写，大的方向就不会错

流程

• 明确check函数是检查两个子树是否对称的方法，即检查两个基本单元是否对称的方法，基本单元是一个父节点，两个左右的孩子
• 那么首先判断给定的两个父节点（left,right）是否为空，如果其中一个为空，那么直接判断两个节点是否相等即可。
• 其次检查两个父节点的值
• 最后检查左右孩子是否对称
• 返回即可

即使一下子写不出递归函数，但是按照定义去写递归，那么即使我们很难透彻递归，我们也能够把题做好

代码

/**
 * 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 check(root.left, root.right);
    }
    public boolean check(TreeNode left, TreeNode right) {
        // 首先检查两个节点是否为null，判断条件是：只要有一个节点为空，那么就判断两个节点是否同时为null
        if(left==null || right==null) return left==right;

        // 判断完成两个节点都不为null后，那么判断两个节点的值是否相等
        if(left.val != right.val) return false;

        // 最后判断当前的树是否对称，即三个节点看成一棵树，判断左节点和右节点的孩子
        return check(left.left, right.right) && check(left.right, right.left);
    }
}

做题永远是思路最重要，一定要理清楚从哪里开始，如果不知道从哪里开始，多看别人的做题记录，寻找自己的感觉，没有捷径可以走。