tag9:树 二叉树的直径

leetcode543. 二叉树的直径

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

示例 :

给定二叉树

          1

        / \

        2  3

      / \   

      4  5   

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

思路整理：

一、直接递归

1、最大节点数：左节点深度+右节点深度+1，最多边数：L+R

2、不断遍历，左右节点

但注意：递归搜索每个节点并设一个全局变量记录最大值

递归代码：

（1）求直径（2）直径L+R\左子树的直径\右子树的直径的最大值

二、利用全局变量记录最大值

代码如下：

class Solution:

    def diameterOfBinaryTree(self, root: TreeNode) -> int:

        if not root:

            return 0

        def depth(root):

            if not root:

                return 0

            left=depth(root.left)

            right=depth(root.right)

            return max(left,right)+1

        left=depth(root.left)

        right=depth(root.right)

        ld=self.diameterOfBinaryTree(root.left)

        rd=self.diameterOfBinaryTree(root.right)

        tmp=max(rd,ld)

        return max(left+right,tmp)

代码如下：

class Solution:

    def diameterOfBinaryTree(self, root: TreeNode) -> int:

        if not root:

            return 0

        self.ans=1

        def depth(root):

            if not root:

                return 0

            left=depth(root.left)

            right=depth(root.right)

            self.ans=max(self.ans,left+right+1)

            return max(left,right)+1

        depth(root)

        return self.ans-1

-20200104