二叉树的直径

# -*- coding: utf-8 -*-

import sys

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


class BT(object):
    def __init__(self):
        self.root = None

    def levelOrderToBT(self, nums):
        n = len(nums)

        if n > 0:
            self.root = TreeNode(nums[0])
            queue, idx = [self.root], 1
            while queue and idx < n:
                curNode = queue.pop(0)
                curNode.left = TreeNode(nums[idx]) \
                    if nums[idx] != None else None
                if curNode.left:
                    queue.append(curNode.left)
                curNode.right = TreeNode(nums[idx + 1]) \
                    if idx + 1 < n and nums[idx + 1] != None else None
                if curNode.right:
                    queue.append(curNode.right)
                idx += 2

        return self.root

    @staticmethod
    def levelOrder(root):
        if not root:
            return []

        queue, res = [root], []
        while queue:
            node = queue.pop(0)
            if node:
                res.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            else:
                res.append(None)
        while res and res[-1] == None:
            res.pop()

        return res


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return int整型
#
class Solution:
    """
    题目：
        NC195 二叉树的直径
        https://www.nowcoder.com/practice/15f977cedc5a4ffa8f03a3433d18650d?tpId=117&&tqId=39370&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
    参考：
        大神：君无颜
    算法：
        关键点：以当前节点为头结点的树，直径就是左右两个子树的高度相加，故最大直径属于在如下三种情况之一：
            1. 最大直径包含root：以 root 为头结点的树，最大直径就是左右两个子树的高度相加
            2. 最大直径出现在root的左子树：左子树的直径是以 root->left 为头结点的树，最大直径同理
            3. 最大直径出现在root的右子树：右子树的直径是以 root->right 为头结点的树，最大直径同理
        最后，取三者最大值即可。
    复杂度：
        时间复杂度：O(N)，N为二叉树的节点数
        空间复杂度：O(H)，H为二叉树的高度
    """

    def diameterOfBinaryTree(self, root):
        # write code here
        def getHeight(root):
            if not root:  # 空子树的高度为0
                return 0
            lHeight, rHeight = getHeight(root.left), getHeight(root.right)
            self.res = max(self.res, lHeight + rHeight)
            return lHeight + 1 if lHeight > rHeight else rHeight + 1

        self.res = 0
        sys.setrecursionlimit(1500)
        getHeight(root)
        return self.res


if __name__ == '__main__':
    s = Solution()

    # nums = [1, 2, 3, None, None, 4, 5]

    # nums = [1, 2, 3, None, None, 4, 5, 9, None, None, 6, None, 7, None, 8]

    # nums = [1, 2, 3]

    nums = []

    bt = BT()
    bt1 = bt.levelOrderToBT(nums)
    # print BT.levelOrder(bt1)

    res = s.diameterOfBinaryTree(bt1)
    print res