当前位置:网站首页>"104 Maximum Depth of Binary Trees" in LeetCode's Day 12 Binary Tree Series
"104 Maximum Depth of Binary Trees" in LeetCode's Day 12 Binary Tree Series
2022-08-11 03:52:00 【small double】
LeetCode 104 二叉树的最大深度
题目描述
给定一个二叉树,找出其最大深度
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数.
说明: 叶子节点是指没有子节点的节点.
示例
给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 .
题目解析
For those who have studied data structures, this problem can be written in a recursive way very quickly.The depth of the tree is also the height of the tree,When computing, you can generally use a depth-first search method to recursively traverse the tree structure,Of course, the recursive method can also be implemented using the stack method.下面是两种实现方式:
使用递归
对于任意一个节点,If its left and right subtrees are empty,It means that the tree has only one node,返回1.否则,Recursively compare the size of the left and right subtrees,Go to max plus1(Represents the root node of the tree),代码如下:
public int maxDepth(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 1; } return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; //Compare the maximum value of the depth of the left and right subtrees plus the root node }
程序运行结果:
Non-recursive method using stack structure:
对于非递归的方法,使用队列也是可以的,The idea corresponding to the queue is breadth-first search,Or a tree level traversal,And the depth-first search is changed to a non-recursive way to use a stack structure,After all, recursion itself is also implemented using the system stack structure.
具体思路如下:
- 创建一个空栈,push the root to the stack;
- Loop through the stack when the stack is not empty,每次查看(Note that it is not a popup)The element pointed to by the top of the stack pointer,If the left and right subtrees of the top node of the stack are empty,the top of the stack出栈(Corresponding to recursion, the return is changed to recursive operation),树的深度-1,继续循环;
- If there is a left subtree at the top node of the stack,则将左子树入栈,And set the left child of the top-of-stack pointer to null,Avoid pushing the left subtree to the stack again next time.树的深度加1,继续循环遍历;
- If the top node of the stack has a right subtree,则将右子树入栈,And the right child of the stack top pointer is nulled,树的深度+1;继续循环遍历.
Because the depth of the tree cannot be accumulated multiple times during implementation,Therefore, a maximum depth is set to record the maximum depth of the currently traversed tree.Illustrate with examples:
代码如下:
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Stack<TreeNode> stack = new Stack<>();
stack.add(root);
int deep = 1;
int maxDeep = 1;
while (!stack.empty()) {
TreeNode peek = stack.peek(); //peekTo view the top of the stack pointer
if (peek.left == null && peek.right == null) {
//Leaf nodes pop the top of the stack
deep--;
stack.pop();
continue;
}
if (peek.left != null) {
//Look at the left subtree first,It's like recursively traversing the left subtree
stack.add(peek.left);
peek.left = null;
deep++;
if (deep > maxDeep) {
//For greater depths, change the value of max depth
maxDeep++;
}
continue;
}
if (peek.right != null) {
stack.add(peek.right);
peek.right = null;
deep++;
if (deep > maxDeep) {
maxDeep++;
}
}
}
return maxDeep;
}
然而...The program doesn't seem to work so well...
边栏推荐
- En-us is an invalid culture error solution when Docker links sqlserver
- Interchangeability and Measurement Techniques - Tolerance Principles and Selection Methods
- 【FPGA】day21-移动平均滤波器
- QueryDet:级联稀疏query加速高分辨率下的小目标检测
- AI + medical: for medical image recognition using neural network analysis
- 什么是机器强化学习?原理是什么?
- 按摩椅控制板的开发让按摩椅变得简约智能
- 机器学习可以应用在哪些场景?机器学习有什么用?
- Enter the starting position, the ending position intercepts the linked list
- How to rebuild after pathman_config and pathman_config_params are deleted?
猜你喜欢
【FPGA】day22-SPI protocol loopback
Unity2D animation (1) introduction to Unity scheme - animation system composition and the function of use
Build Zabbix Kubernetes cluster monitoring platform
LeetCode刷题第17天之《3 无重复字符的最长子串》
Interchangeability and Measurement Techniques - Tolerance Principles and Selection Methods
Redis老了吗?Redis与Dragonfly性能比较
Detailed explanation of VIT source code
How does MSP430 download programs to the board?(IAR MSPFET CCS)
移动端地图开发选择哪家?
console.log alternatives you didn't know about
随机推荐
What should I do if the channel ServerID is incorrect when EasyCVR is connected to a Hikvision Dahua device and selects another cluster server?
二叉树相关代码题【较全】C语言
Interchangeability Measurements and Techniques - Calculation of Deviations and Tolerances, Drawing of Tolerance Charts, Selection of Fits and Tolerance Classes
[FPGA] day19- binary to decimal (BCD code)
Differences and connections between distributed and clustered
Leetcode 669. 修剪二叉搜索树
What is Machine Reinforcement Learning?What is the principle?
Getting Started with Raspberry Pi (5) System Backup
荣威imax8ev魔方电池安全感,背后隐藏着哪些黑化膨胀?
用户如何克服程序化交易中的情绪问题?
The last update time of the tables queried by the two nodes of the rac standby database is inconsistent
多串口RS485工业网关BL110
E-commerce project - mall time-limited seckill function system
LeetCode热题(12.买卖股票的最佳时机)
MYSQLg高级------回表
js 将字符串作为js执行代码使用
shell监视gpu使用情况
Is Redis old?Performance comparison between Redis and Dragonfly
LeetCode Brush Questions Day 11 String Series "58 Last Word Length"
Audio codec, using FAAC to implement AAC encoding