求二叉树的深度 python

　　二叉树有深度和高度两个属性，一个节点的深度指的是从根节点到该节点路径的长度，根节点的深度为1；一个节点的高度指的是从该节点到叶子节点所有路径上包含节点个数的最大值。叶子节点的高度为1，往上节点的高度依次递增。所以要求二叉树的深度，我们要求出从根节点到叶子结点最长路径的长度，从根节点到所有的叶子结点，实际就是在遍历这棵树，使用深度优先遍历可以解决这个问题。

　　首先还是定义一颗二叉树的类。

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

　　然后，为了得到从根节点到叶子结点路径的长度，我们从根节点出发，进行深度优先遍历，当遍历到一个叶子结点时，就计算出了一条路径的长度，这时返回到上一层，即叶子结点的父亲节点，继续对另一颗子树进行深度优先遍历，计算其他路径的长度。因此，这里有两个问题，第一，我们需要一个变量保存当前遍历路径的长度，它保存的一定是当前遍历的路径长度，应该作为函数的参数（深度优先遍历的函数）；第二，当遍历到叶子节点时，我们要判断这条路径的长度是否是最长的，因此还需要一个变量来保存当前最长的路径长度，它不会随着函数的迭代改变，应当是一个全局变量，代码如下。

class Solution:
     #二叉树的深度
    def TreeDepth(self, pRoot):
    # write code here
        global maxdepth#全局变量保存当前最长的路径长度
        maxdepth=0
        def DfsTree(root,depth=0):#depth是当前的路径长度
            global maxdepth
            if root:#节点非空，路径长度加1
                depth+=1
            if root.left:#左子树非空，继续遍历左子树
                DfsTree(root.left,depth)
            if root.right:#右子树非空，继续遍历右子树
                DfsTree(root.right,depth)
            if not root.left or root.right:#左右子树都是空的，即该节点是一个叶子结点，则判断depth是不是最长的路径
                if depth>maxdepth:
                    maxdepth=depth
        if root:
            DfsTree(root)
        return maxdepth