当前位置:网站首页>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/
边栏推荐
- [interview arrangement] 0211 game engine server
- 变量与常量
- Debezium系列之:源码阅读之BinlogReader
- The free styling service of Dyson's official direct store is now open for appointment. Pioneer Technology interprets the styling concept of hair care and helps consumers unlock diversified and shiny s
- Line test - graphic reasoning -5- one stroke class
- OpenGL configure assimp
- PHP records the pitfalls encountered in the complete docking of Tencent cloud live broadcast and im live group chat
- Antd date component appears in English
- OpenGL homework - Hello, triangle
- Ni9185 and ni9234 hardware settings in Ni Max
猜你喜欢
Basic knowledge of linked list
What does it mean to prefix a string with F?
UWA Q & a collection
CTF练习
Remember aximp once Use of exe tool
Robot autonomous exploration series papers environment code
Leetcode1984. Minimum difference in student scores
How to judge whether the input content is "number"
0-5vac to 4-20mA AC current isolated transmitter / conversion module
Line test - graphic reasoning - 4 - alphabetic class
随机推荐
变量与常量
Revit secondary development - cut view
行测-图形推理-7-相异图形类
LeetCode206. Reverse linked list [double pointer and recursion]
0-5VAC转4-20mA交流电流隔离变送器/转换模块
How pyGame rotates pictures
Leetcode1984. Minimum difference in student scores
行测-图形推理-1-汉字类
Variables and constants
Unity technical notes (II) basic functions of scriptableobject
ASEMI整流桥KBPC1510的型号数字代表什么
ASP.NET Core入门五
Revit secondary development - modify wall thickness
[azure microservice service fabric] start the performance monitor in the SF node and set the method of capturing the process
Take full control! Create a "leading cockpit" for smart city construction
Kaggle-Titanic
Form组件常用校验规则-2(持续更新中~)
行测-图形推理-8-图群类
Use partial derivatives to display normals in unity
. Net automapper use