树的高度

题目描述

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

note：

注意递归里面的变量，全局变量和局部变量

 1 # -*- coding:utf-8 -*-
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 class Solution:      
 8     def TreeDepth(self, pRoot):
 9         # write code here
10         if not pRoot:
11             return 0
12         if not pRoot.left and not pRoot.right: # 叶子节点返回1
13             return 1
14         return max(self.TreeDepth(pRoot.left) +1,self.TreeDepth(pRoot.right)+1)
15         
16

下面这个代码，报错，right_d在赋值前是局部变量

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:     
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot:
            return 0
        if not pRoot.left and not pRoot.right:
            return 1
        if pRoot.left:
            left_d = self.TreeDepth(pRoot.left) +1
        if pRoot.right:
            right_d = self.TreeDepth(pRoot.right)+1
        return max(left_d,right_d)

修改成功（以下代码是正确的）

 1 # -*- coding:utf-8 -*-
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 class Solution:     
 8     def TreeDepth(self, pRoot):
 9         # write code here
10         if not pRoot:
11             return 0
12         #if not pRoot.left and not pRoot.right:
13         #    return 1
14         #if pRoot.left:
15         left_d = self.TreeDepth(pRoot.left) +1
16         #if pRoot.right:
17         right_d = self.TreeDepth(pRoot.right)+1
18         return max(left_d,right_d)