第六题

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2020/5/25 下午5:10
# @Author : Yuxiaoxue# @Site : 
# @File : ques6.py
# @Software: PyCharm

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

'''
class TreeNode:
    def __init__(self,x):
        self.value = x
        self.left = None
        self.right = None

'''
解题思路：
如果根节点是空，返回0 
如果左右子树都是空，树的深度为1
如果左子树是空，树的深度等于右子树的深度+1，如果右子树是空，树的深度等于左子树的深度+1
如果左子树和右子树都不是空，树的深度等于左子树和右子树中比较大的一个+1
'''
def TreeDepth(self,pRoot):
    if pRoot == None:
        return 0
    if pRoot.left == None:
        return self.TreeDepth(pRoot.right) + 1
    if pRoot.right == None:
        return self.TreeDepth(pRoot.left) + 1
    else:
        return max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1