题目

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

示例 :
给定二叉树

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/diameter-of-binary-tree

题解

题目的意思是，求树里最长的路径，也就是求左右子树深度之和的最大节点，需要注意的是这个节点不一定经过根噢。比如下图：

[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]

在这歌树中明显节点6的左右子树深度之和才是最大的。 

思路

我的思路是，遍历这棵树每个节点，这样每个节点的左右子树深度和都能求到，然后作比较即可。

递归解法

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:

        res = 1

        def dfs(p):
            nonlocal res
            if not p:
                return 0

            l = dfs(p.left)
            r = dfs(p.right)
            res = max(res, l+r+1)

            return max(l, r) + 1

        dfs(root)
        return res - 1

堆栈解法

注意堆栈解要用后序遍历，左右子树都遍历完才可以进行求和操作

class SolutionMy:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        p = root
        s = []
        r = None
        root.dept = 0
        maxDept = 0

        while s or p:
            while p:
                s.append(p)
                p = p.left

            t = s[-1] if s else None
            if t.right and t.right != r:
                p = t.right  
            else:
                t = s.pop()
                r = t
                if not (t.left or t.right):
                    t.dept = 1

                else:
                    lDept = t.left.dept if t.left else 0
                    rDept = t.right.dept if t.right else 0
                    t.dept = max(lDept, rDept) + 1
                    maxDept = max(maxDept, lDept+rDept+1)
                    p = None

        return max(1, maxDept) -1