美文网首页
[easy+][Tree]543.

[easy+][Tree]543.

作者: 小双2510 | 来源:发表于2017-11-09 23:09 被阅读0次

    原题是:

    Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

    Example:
    Given a binary tree
    1
    /
    2 3
    / \
    4 5
    Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

    Note: The length of path between two nodes is represented by the number of edges between them.

    思路是:

    之前写过一个简单题,是求一个树的最大深度,这个深度不只是节点上的边,是指节点最深的路径上所有的节点数。这里可以用到这个函数。
    最大diameter,必然是经过树或者他某个子树的root,所以这个路径是由某个节点的左右子树的最大深度的和构成。我们只要找到哪个子树拥有最大的过其root的路径就可以了。

    代码是:

    # 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 diameterOfBinaryTree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if root == None:
                return 0
            elif not (root.left or root.right):
                return 0
            
            ans = self.maxDepth(root.left) + self.maxDepth(root.right)
            Left = self.diameterOfBinaryTree(root.left)
            Right = self.diameterOfBinaryTree(root.right)
            res = max(max(ans,Left),Right)
            
            return res
            
        #return any tree's maximum depth(including root)
        def maxDepth(self,root): 
            if root == None:
                return 0
            
            Left = self.maxDepth(root.left)
            Right = self.maxDepth(root.right)
            return max(Left,Right) + 1
    

    相关文章

      网友评论

          本文标题:[easy+][Tree]543.

          本文链接:https://www.haomeiwen.com/subject/duhvmxtx.html