剑指38-二叉树的深度

Posted on | In |

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

循环和递归，递归函数的参数是节点root及其父节点的深度k，以及一个全局的引用变量dpthlist（用对象的成员变量也行）用来存储叶节点的深度。

  • 一旦遇到空节点，返回，存储其父节点也是叶节点的深度进dpthlist。
  • 非空节点，分别对其左右孩子节点执行递归函数。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def TreeDepth(self, root):
        dpthlist = [0]
        def recur(root, k, dpthlist):
            # 首次调用recur(root, 0, dpthlist)，故k是root父节点的深度
            if not root:
                dpthlist.append(k)
                return
            recur(root.left, k+1, dpthlist)
            recur(root.right, k+1, dpthlist)
        recur(root, 0, dpthlist)
        return max(dpthlist)

上面版本在叶节点上获知深度，而如下版本在根节点获知深度，代码更简洁：

1
2
3
4
5
6
7
class Solution:
    def TreeDepth(self, root):
        if root is None:
            return 0
        if not(root.left or root.right):
            return 1
        return 1 + max(self.TreeDepth(root.left), self.TreeDepth(root.right))