当前位置:网站首页>[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
边栏推荐
- Why do some people say SCM is simple and I have to learn it so hard?
- Shell-awk命令的使用
- [二叉数] 二叉树的最大深度+N叉树的最大深度
- 圆环回原点问题-字节跳动高频题
- QT modification UI does not take effect
- C dapper basically uses addition, deletion, modification and query transactions, etc
- Metaprogramming, proxy and reflection
- If you start from zero according to the frame
- .Net Core3. 1 use razorengine NETCORE production entity generator (MVC web version)
- Self use learning notes - connected and non connected access to database
猜你喜欢
394. 字符串解码-辅助栈
For the space occupation of the software, please refer to the installation directory
How to change input into text
[difference between Oracle and MySQL]
ClickHouse-表引擎
Qt 修改UI没有生效
01-初识sketch-sketch优势
Collection of common SQL statements
[logical fallacy in life] Scarecrow fallacy and inability to refute are not proof
Double pointer advanced -- leetcode title -- container with the most water
随机推荐
470. Rand10() is implemented with rand7()
Shell - introduction, variables, and basic syntax
How to sort the numbers with text in Excel from small to large instead of the first number
Clickhouse SQL operation
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
Using quartz under. Net core - [1] quick start
JS, entries(), keys(), values(), some(), object Assign() traversal array usage
198. 打家劫舍-动态规划
Allowed latency and side output
古代埃及希腊,数学用的什么进制
41. The first missing positive number
[二叉数] 二叉树的最大深度+N叉树的最大深度
C语言程序设计之函数的构造
Qt 修改UI没有生效
Seven cattle upload pictures (foreground JS + background C API get token)
Deep understanding of control inversion and dependency injection
394. 字符串解码-辅助栈
470. 用 Rand7() 实现 Rand10()
Indexes and views in MySQL
Webapi + form form upload file