当前位置:网站首页>[binary number] maximum depth of binary tree + maximum depth of n-ary tree
[binary number] maximum depth of binary tree + maximum depth of n-ary tree
2022-04-23 17:36:00 【Alson_ Code】
One 、 Title Description
Link to the original text :104. The maximum depth of a binary tree
A detailed description :
The depth of a binary tree is the number of nodes in the longest path from the root node to the farthest leaf node .
explain : A leaf node is a node that has no children .
Example :
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
Return to its maximum depth 3 .
Two 、 Thought analysis
Once before The maximum depth of the binary number , In fact, it uses hierarchical traversal ! This time we use recursion !
First of all, let's understand a sentence : Preorder traversal is depth , Post order traversal is depth , Depth equals height !
From this sentence, we can see two solutions , A preamble , A post order !
Let's talk about the sequence first ( Recursive Trilogy ):
- Determine the parameters and return values , The return value is int Depth of type , Parameters are subtrees + depth
- Termination conditions , If the subtree is null Returns the current depth
- Single layer logic is , Traverse the left node , After traversing the right node , Compare the size !
Let's talk about the preface ( Recursive Trilogy ):
- Because the first root is on the left and right , So you can't return a value at the root , So the return value is void, Parameter or subtree + depth
- The termination condition is to find that if the left and right subtrees are empty, it will end
- Compare with the current depth and root to get the maximum value , Then recursively obtain the maximum value in the left and right subtrees !
3、 ... and 、AC Code
After the sequence traversal :
/** * Definition for a binary tree node. * 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; * } * } */
class Solution {
public int maxDepth(TreeNode root) {
return getDepth(root, 0);
}
public int getDepth(TreeNode root, int depth){
if (root == null) return depth;
int leftDepth = getDepth(root.left, depth + 1);// Left
int rightDepth = getDepth(root.right, depth + 1);// Right
return leftDepth > rightDepth ? leftDepth : rightDepth;// root
}
}
The former sequence traversal :
/** * Definition for a binary tree node. * 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; * } * } */
class Solution {
int result = 0;
public int maxDepth(TreeNode root) {
if (root == null) return result;
getDepth(root, 1);
return result;
}
public void getDepth(TreeNode root, int depth){
result = result > depth ? result : depth;// root
if (root.left != null){
depth++;
getDepth(root.left, depth);
depth--;// Return to the original value , Otherwise, the right subtree will be found on the basis of the left subtree !
}
if (root.right != null){
depth ++;
getDepth(root.right, depth);
depth--;
}
}
}
Four 、 summary
- depth = Height , Depth is from root to leaf node , Height is from leaf to root !
5、 ... and 、 Consolidation exercises
/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */
class Solution {
public int maxDepth(Node root) {
return getDepth(root, 1);
}
public int getDepth(Node root, int depth){
if (root == null) return 0;
int maxDepth = depth;
for (int i = 0; i < root.children.size(); i++){
int tmpDepth = getDepth(root.children.get(i), depth + 1);
maxDepth = tmpDepth > maxDepth ? tmpDepth : maxDepth;
}
return maxDepth;
}
}
Thanks for reading , I am a Alson_Code, One likes to complicate simple problems , A program that simplifies complex problems !
版权声明
本文为[Alson_ Code]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231728041597.html
边栏推荐
- ClickHouse-表引擎
- Shell-sort命令的使用
- Collection of common SQL statements
- 为什么有些人说单片机简单,我学起来这么吃力?
- Use of shell sed command
- Halo 开源项目学习(二):实体类与数据表
- Manually implement simple promise and its basic functions
- Flash project cross domain interception and DBM database learning [Baotou cultural and creative website development]
- Self use learning notes - connected and non connected access to database
- Indexes and views in MySQL
猜你喜欢
470. Rand10() is implemented with rand7()
440. 字典序的第K小数字(困难)-字典树-数节点-字节跳动高频题
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
RPC核心概念理解
92. Reverse linked list II byte skipping high frequency question
STM32 entry development board choose wildfire or punctual atom?
ASP. Net core JWT certification
快时钟同步慢时钟域下的异步控制信号slow clk to fast clk
Learning record of uni app dark horse yougou project (Part 2)
Using quartz under. Net core -- operation transfer parameters of [3] operation and trigger
随机推荐
Generating access keys using JSON webtoken
ASP. Net core reads the configuration file in the class library project
01 - get to know the advantages of sketch sketch
If you start from zero according to the frame
基于51单片机红外无线通讯仿真
双指针进阶--leetcode题目--盛最多水的容器
198. Looting - Dynamic Planning
Using quartz under. Net core - [1] quick start
JVM class loading mechanism
Manually implement simple promise and its basic functions
Metaprogramming, proxy and reflection
386. 字典序排数(中等)-迭代-全排列
Perception of linear algebra 2
Ouvrir des contrats à terme, ouvrir des comptes en nuage ou faire confiance aux logiciels des sociétés à terme?
Router object, route object, declarative navigation, programmed navigation
Clickhouse SQL operation
The system cannot be started after AHCI is enabled
41. 缺失的第一个正数
Collection of common SQL statements
[WPF binding 3] listview basic binding and data template binding