当前位置:网站首页>Leetcode-543. Diameter of Binary Tree
Leetcode-543. Diameter of Binary Tree
2022-07-07 07:30:00 【Eistert】
subject
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
Example 1:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2]
Output: 1
Constraints:
The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100
solution
Method 1 : Depth-first search
First, we know that the length of a path is the number of nodes that the path passes through minus one , So find the diameter ( That is, find the maximum value of the path length ) Equivalent to finding the maximum number of nodes the path passes through minus one .
Any path can be regarded as starting from a node , From the stitching of the paths traversed downward by his left son and right son .
As shown in the figure, we can know the path [9, 4, 2, 5, 7, 8] Can be seen as 2 As a starting point , The path traversed down from his left son [2, 4, 9] And the path traversed down from his right son [2, 5, 7, 8] Spliced to get .
Suppose we know that the left son of the node traverses down the maximum number of nodes LL ( That is, the depth of the subtree with the left son as the root ) And its right son traverse down the maximum number of nodes R ( That is, the depth of the subtree with the right son as the root ), Then the maximum number of nodes that the path starting from this node passes through is L+R+1 .
We remember the nodes node The maximum number of nodes passed by the path as the starting point is node, Then the diameter of the binary tree is all the nodes node Minus one... From the maximum .
The final algorithm flow is : We define a recursive function depth(node) Calculation node, Function returns the depth of the subtree whose node is the root .
First, recursively call the left son and the right son to find the depth of the subtree with their roots LL and RR , Then the depth of the subtree whose node is the root is max(L,R)+1
Of this node d node The value is
L+R+1
Recursively search each node and set a global variable ans Record d node The maximum of , Finally back to ans-1 Is the diameter of the tree .
Code
/** * 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 maxd = 0;
public int diameterOfBinaryTree(TreeNode root) {
getDepth(root);
return maxd;
}
public int getDepth(TreeNode node){
if(node == null){
return 0;
}
int L,R;
L = getDepth(node.left);
R = getDepth(node.right);
maxd = Math.max(L+R,maxd);
return Math.max(L,R) + 1;
}
}
Complexity analysis
Time complexity :O(N), among NN Is the number of nodes in the binary tree , That is, the time complexity of traversing a binary tree , Each node is accessed only once .
Spatial complexity :O(Height), among Height Is the height of the binary tree . Because the recursive function needs to allocate stack space for each layer of recursive function in the recursive process , So extra space is needed here, and that space depends on the depth of the recursion , The depth of recursion is obviously the height of binary tree , And each recursive call uses only constant variables , So the required space complexity is O(Height).
source
author :LeetCode-Solution
link :https://leetcode-cn.com/problems/diameter-of-binary-tree/solution/er-cha-shu-de-zhi-jing-by-leetcode-solution/
source : Power button (LeetCode)
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .
边栏推荐
- Causes and solutions of oom (memory overflow)
- Blue Bridge Cup Netizen age (violence)
- Composition API premise
- 毕设-基于SSM大学生兼职平台系统
- Special behavior of main function in import statement
- [semantic segmentation] - multi-scale attention
- 【Liunx】进程控制和父子进程
- Communication of components
- English translation is too difficult? I wrote two translation scripts with crawler in a rage
- How can a 35 year old programmer build a technological moat?
猜你喜欢
LC interview question 02.07 Linked list intersection & lc142 Circular linked list II
Implementation of AVL tree
考研失败,卷不进大厂,感觉没戏了
mips uclibc 交叉编译ffmpeg,支持 G711A 编解码
Le Service MySQL manque dans le service informatique
Implementing data dictionary with JSP custom tag
Redis data migration
07_ Handout on the essence and practical skills of text measurement and geometric transformation
Wechat applet full stack development practice Chapter 3 Introduction and use of APIs commonly used in wechat applet development -- 3.9 introduction to network interface (IX) extending the request3 met
Detailed explanation of neo4j installation process
随机推荐
$parent (get parent component) and $root (get root component)
C language (high-level) data storage + Practice
Summary of customer value model (RFM) technology for data analysis
Pass child component to parent component
Asynchronous components and suspend (in real development)
Special behavior of main function in import statement
一、Go知识查缺补漏+实战课程笔记 | 青训营笔记
Implementation of AVL tree
Interviewer: what development models do you know?
JS decorator @decorator learning notes
Tujia, muniao, meituan... Home stay summer war will start
Advanced level of C language (high level) pointer
按键精灵脚本学习-关于天猫抢红包
Chinese and English instructions prosci LAG-3 recombinant protein
Several important steps to light up the display
Stockage et pratique des données en langage C (haut niveau)
Detailed explanation of transform origin attribute
[explanation of JDBC and internal classes]
How does an enterprise manage data? Share the experience summary of four aspects of data governance
抽丝剥茧C语言(高阶)数据的储存+练习