LeetCode 104.二叉树的最大深度 python/sca

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))
  }
}

最后

欢迎交流和补充