Codility每周一课：P99.3 TreeHeight

0.png

P99.3 TreeHeight

Compute the height of a binary tree.

• P99.3 二叉树的深度
  计算二叉树的深度

在这个问题中，使用指针数据结构表示二叉树。二叉树由一个空树或者一个具有整数值的根节点和另外两个子二叉树（称为左子树和右子树）组成。

例如，下图显示了一个由6个节点组成的二叉树。它的根节点的值为5，其左子树和右子树的根节点的值分别为3和10。值为10的节点的右子树，值为20，21和1的节点的 左、右子树都是空树。

image

二叉树中的路径是节点的非空序列，可以通过指针来遍历这些节点。路径的长度是它所遍历的指针数。也就是说，节点序列P[0], P[1], ..., P[K]是长度为K的路径 ，对于0 ≤ I < K，如果P[I+1]是左子树或者右子树P[I]的根节点。

例如，值为5、3、21的节点序列是上图中树中长度为2的路径。值为10、1的节点序列是长度为1的路径。值为21、3、20的节点序列不是路径。 二叉树的深度定义为树中最长路径的长度。注意：只有一个节点组成的树的深度为0，通常情况下，空树的深度为-1。因此，上图中树的深度为2。

编写函数：

def solution(T)

给定一个由N个节点组成的非空二叉树T，则返回其深度。例如，给定上图中所示的树T，函数应该返回2。请注意，节点中的值没有意义。

使用指针数据结构给出二叉树。假设：

class Tree(object):  
    x = 0  
    l = None  
    r = None

空树由空指针表示（用None表示）。非空树由指向表示其根节点的指针表示。属性X保存根节点的值，而属性l和r分别保存二叉树的左子树和右子树。 空的二叉树用none表示。非空树表示为（x，l，r），其中x是根中包含的值，l和r分别表示左子树和右子树。上图中的树可以表示为：

(5, (3, (20, None, None), (21, None, None)), (10, (1, None, None), None))

假定：

1. N是区间[1，1000]内的整数；
2. 树T的深度不大于500；

• 解题思路

递归计算二叉树的深度，直到二叉树变为None。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 99：Future training
# P 99.3 TreeHeight



def solution_(T):
    """
    返回二叉树T的最大深度，采用递归的方式
    :param T: 二叉树
    :return: 最大深度
    """
    # 二叉树为空树，层数就是0
    if T is None:
        return 0

    # 左子树的深度
    depth_left = solution_(T.l)
    # 右子树的深度
    depth_right = solution_(T.r)

    # 左、右子树深度较大的，然后加上1
    return max(depth_left, depth_right) + 1


def solution(T):
    """
    需要将最终的树的深度减去1
    :param T: 二叉树
    :return: 树的深度
    """
    return solution_(T) - 1

• 结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image