剑指 Offer —对称的二叉树

复仇Bytedance之路

题目描述：

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

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

输入：root = [1,2,2,3,4,4,3] 输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3] 输出：false

限制：

0 <= 节点个数 <= 1000

题解

涉及到二叉树的题目大概率都会使用到递归

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { if(root==null){ return true; } return mySymmetric(root.left,root.right); } public boolean mySymmetric(TreeNode l,TreeNode r){ //递归结束条件，root为null,说明已经搜索完毕也为出现退出条件 if(l==null&&r==null){ return true; } //退出判断，左右子树有一个不为null if(l==null||r==null){ return false; } //退出判断，当前值是否相等 if(l.val!=r.val){ return false; } //递归判断：左的左子树和右的右子树&&左的右子树和右的左子树。这样才是镜像 return mySymmetric(l.left,r.right)&&mySymmetric(l.right,r.left); } }

写一下不成熟的递归感悟：

递归函数首先就需要写递归的退出条件，在这个地方退出条件是搜索到最后一层没有元素了仍然没有出现false的情况，那么就返回true既然写了true，那么自然也要根据写false最关键的就是写最后的递归逻辑，最难理解的部分，不好想清楚。在这里个人觉得自己拿最开始的去分析，然后写下逻辑就好了。