How to find the maximum depth of python binary tree
This article shows you how to find the maximum depth of the python binary tree, the content is concise and easy to understand, it will definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.
Topic description
Given a binary tree, find out its maximum depth.
The depth of the binary tree is the number of nodes on the longest path from the root node to the furthest leaf node.
Note: a leaf node is a node that does not have child nodes.
Example: given binary tree [3, 9, 20, 10, 5, 5, 5, 7]
three
/\
9 20
/\
15 7
Returns its maximum depth of 3.
The idea of solving the problem
Tag: DFS
Find the termination condition: the current node is empty
Find out the return value: if the node is empty, the height is 0, so it returns 0; if the node is not empty, the maximum height of the left and right subtree is calculated respectively, and adding 1 indicates the height of the current node, and returns this value.
The execution process of a layer: it has been described clearly in the return value section.
Time complexity: O (n)
Code
Java version
/ * *
* Definition for a binary tree node.
* public class TreeNode {
* int val
* TreeNode left
* TreeNode right
* TreeNode (int x) {val = x;}
*}
, /
Class Solution {
Public int maxDepth (TreeNode root) {
If (root = = null) {
Return 0
} else {
Int left = maxDepth (root.left)
Int right = maxDepth (root.right)
Return Math.max (left, right) + 1
}
}
}
JavaScript version
/ * *
* Definition for a binary tree node.
* function TreeNode (val) {
* this.val = val
* this.left = this.right = null
*}
, /
/ * *
* @ param {TreeNode} root
* @ return {number}
, /
Var maxDepth = function (root) {
If (! root) {
Return 0
} else {
Const left = maxDepth (root.left)
Const right = maxDepth (root.right)
Return Math.max (left, right) + 1
}
}
Drawing and interpretation
The above content is how to find the maximum depth of the python binary tree. Have you learned the knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.
