扣初级算法-25-树-对称二叉树
2021/11/25 22:39:56
本文主要是介绍扣初级算法-25-树-对称二叉树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
学习目标:
本次学习目标为 力扣初级算法-树,其中主要的LC如下:
- 对称二叉树
学习内容:
- 验证二叉搜索树 -----([链接](https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn7ihv/)
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [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
解题思路:
-
解法一: 直接递归
-
解题思路:
- 判断树是否对称,则需要从子节点开始比较,两个子节点的值必须相同,并且左子节点的右子节点(如果有)必须等于右子节点的左子节点,左子节点的左子节点必须等于右子节点的右子节点
- 边界问题: 根节点是空节点,则返回 true
- 分析左、右节点的情况,如果两者都是空,则不需要比较,直接return ture
- 如果两个非都是空,再细分 则要判断两者值,同时还需要判断其子节点,可领出不相等的情况直接返回,因为若相等还需要继续递归往下处理
- 继续递归子类
-
代码实现:
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 boolean isSymmetric(TreeNode root) { // 边界问题: 根节点是空节点,则返回 true if (null == root){ return true; } return isSymmetricHelper(root.left, root.right); } private boolean isSymmetricHelper(TreeNode left, TreeNode right) { // 分析左、右节点的情况,如果两者都是空,则不需要比较,直接return ture if (null == left && null == right){ return true; } // 如果两个非都是空,再细分 则要判断两者值,同时还需要判断其子节点,可领出不相等的情况直接返回,因为若相等还需要继续递归往下处理 if (null == left || null == right || right.val != left.val){ return false; } return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left); }
这篇关于扣初级算法-25-树-对称二叉树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南