101对称二叉树
- 原题链接:
- 完成情况:
- 解题思路:
- 参考代码:
原题链接:
101. 对称二叉树
https://leetcode.cn/problems/symmetric-tree/
完成情况:
解题思路:
递归的难点在于:找到可以递归的点 为什么很多人觉得递归一看就会,一写就废。 或者说是自己写无法写出来,关键就是你对递归理解的深不深。
对于此题: 递归的点怎么找?从拿到题的第一时间开始,思路如下:
1.怎么判断一棵树是不是对称二叉树? 答案:如果所给根节点,为空,那么是对称。如果不为空的话,当他的左子树与右子树对称时,他对称
2.那么怎么知道左子树与右子树对不对称呢?在这我直接叫为左树和右树 答案:如果左树的左孩子与右树的右孩子对称,左树的右孩子与右树的左孩子对称,那么这个左树和右树就对称。
仔细读这句话,是不是有点绕?怎么感觉有一个功能A我想实现,但我去实现A的时候又要用到A实现后的功能呢?
当你思考到这里的时候,递归点已经出现了: 递归点:我在尝试判断左树与右树对称的条件时,发现其跟两树的孩子的对称情况有关系。
想到这里,你不必有太多疑问,上手去按思路写代码,函数A(左树,右树)功能是返回是否对称
def 函数A(左树,右树): 左树节点值等于右树节点值 且 函数A(左树的左子树,右树的右子树),函数A(左树的右子树,右树的左子树)均为真 才返回真
实现完毕。。。
写着写着。。。你就发现你写出来了。。。。。。
最后一些小细节,在代码里有注解出来,大家参考时,可以注意一下 |
参考代码:
package 西湖算法题解;public class __101对称二叉树 {public static void main(String[] args) {}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;}}// public class TreeNodepublic boolean isSymmetric(TreeNode root) {//1.递归判断if (root==null){return true;}return CompareIsSymmetric(root.left,root.right);}private boolean CompareIsSymmetric(TreeNode left, TreeNode right) {//全空则为trueif (left==null && right==null){return true;}//一个为空,另一个不为空,则一定是falseif (left == null || right == null){return false;}//如果上面都满足了,则说明该结点的左右结点均存在//但是需要注意,如果左右结点相等,还是无法肯定它们就是对称树,但如果左右节点不相等,则它们一定是非对称树if (left.val != right.val){return false;}//如果相等,则继续往下递归//这里递归也需要注意,即左边的左,对应右边的右;;;;;;左边的右,对应右边的左return CompareIsSymmetric(left.left,right.right) && CompareIsSymmetric(left.right,right.left);}
}