leetcode 543 二叉树的直径

题目

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 : 给定二叉树

1 / \ 2 3 / \ 4 5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

代码

小结：对于每个节点分别求解左、右的深度，两边的深度求和，与全局的直径比较。如果大于，就替换。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def deepPath(self, root): if root == None: return 0 ldp = self.deepPath(root.left) rdp = self.deepPath(root.right) self.res = max(self.res, ldp + rdp) return max(ldp, rdp) + 1 def diameterOfBinaryTree(self, root): """ :type root: TreeNode :rtype: int """ if root == None: return 0 self.res = 0 self.deepPath(root) return self.res