Maximum Depth of Binary Tree
环境：python 3.6，scala 2.11.8
题意
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数
分析
换个角度，假定根节点深度为1，则树中每个节点都携带了节点值和深度。此时可使用二叉树的先序、中序及后序遍历完成。
代码
python
def maxDepth(root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
rs = [0]
def dfs(node, depth):
if node:
if depth > rs[-1]:
rs[-1] = depth
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
dfs(root, 1)
return rs[-1]
def maxDepthV2(root):
if not root: return 0
return 1 + max(maxDepthV2(root.left), maxDepthV2(root.right))
scala
object LC104 {
def maxDepth(root: TreeNode): Int = {
if (root == null) return 0
var currMaxDepth = 1
def dfs(node: TreeNode, depth: Int): Unit =
if (node != null) {
if (depth > currMaxDepth) currMaxDepth = depth
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
}
dfs(root, 1)
currMaxDepth
}
def maxDepthV2(root: TreeNode): Int = {
if(root == null) return 0
1 + scala.math.max(maxDepthV2(root.left), maxDepthV2(root.right))
}
}
最后
欢迎交流和补充
