当前位置:网站首页>Sword finger offer 28 Symmetric binary tree
Sword finger offer 28 Symmetric binary tree
2022-07-07 22:52:00 【Yes' level training strategy】
subject : Please implement a function , Used to judge whether a binary tree is symmetrical . If a binary tree is the same as its mirror image , So it's symmetrical .
for example , Binary tree [1,2,2,3,4,4,3] It's symmetrical .
But the next one [1,2,2,null,3,null,3] It's not mirror symmetric :
Example 1:
Input :root = [1,2,2,3,4,4,3]
Output :true
Example 2:
Input :root = [1,2,2,null,3,null,3]
Output :false
According to the meaning , In fact, it is to compare the left and right subtrees .
First judge the root node's left Whether or not right equal , If so, continue recursive judgment , The objects of judgment are left.left and right.right、left.right and right.left.
In this way, recursive judgment in turn , The idea should be very clear , If you encounter any nonconformity in the middle, you can return directly .
Let's take a look at the code :
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode left, TreeNode right) {
if ((left == null && right != null) || (left != null && right == null)) {
return false;
}
if (left == null && right == null) {
return true;
}
if (left.val != right.val) {
return false;
}
return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}
}
This is the most obvious and direct judgment , therefore isSymmetric The code can be optimized :
class Solution {
private boolean isSymmetric(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null || left.val != right.val) {
return false;
}
return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}
}
Time complexity O(N), Spatial complexity O(N)
Okay , A simple question !
https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
边栏推荐
- 行测-图形推理-3-对称图形类
- OpenGL jobs - shaders
- IP network active evaluation system -- x-vision
- Use partial derivatives to display normals in unity
- JS number is insufficient, and 0 is added
- UWA问答精选
- Revit secondary development - wall opening
- Leetcode206. Reverse linked list
- Variables and constants
- Write in front -- Talking about program development
猜你喜欢
How to choose the appropriate automated testing tools?
ASEMI整流桥KBPC1510的型号数字代表什么
UnicodeDecodeError: ‘gbk‘ codec can‘t decode byte 0xf9 in position 56: illegal multibyte sequence
IP network active evaluation system -- x-vision
VTOL in Px4_ att_ Control source code analysis [supplement]
Redis official ORM framework is more elegant than redistemplate
Signal feature extraction +lstm to realize gear reducer fault diagnosis -matlab code
Leetcode interview question 02.07 Linked list intersection [double pointer]
GBU1510-ASEMI电源专用15A整流桥GBU1510
0-5VAC转4-20mA交流电流隔离变送器/转换模块
随机推荐
[interview arrangement] 0211 game engine server
Visual studio 2019 installation
Debezium series: binlogreader for source code reading
Two methods of calling WCF service by C #
Variables and constants
Px4 autonomous flight
新版代挂网站PHP源码+去除授权/支持燃鹅代抽
Revit secondary development - intercept project error / warning pop-up
Debezium series: support the use of variables in the Kill Command
Attitude estimation (complementary filtering)
ASP. Net core introduction V
Unity technical notes (I) inspector extension
Xcode modifies the default background image of launchscreen and still displays the original image
php 记录完整对接腾讯云直播以及im直播群聊 所遇到的坑
Aspose. Words merge cells
Revit secondary development - project file to family file
Basic knowledge of binary tree
行測-圖形推理-4-字母類
Yarn开启ACL用户认证之后无法查看Yarn历史任务日志解决办法
vite Unrestricted file system access to