题目

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

示例 :
给定二叉树

          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 = 1def dfs(p):nonlocal resif not p:return 0l = dfs(p.left)r = dfs(p.right)res = max(res, l+r+1)return max(l, r) + 1dfs(root)return res - 1

堆栈解法

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

class SolutionMy:def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:if not root:return 0p = roots = []r = Noneroot.dept = 0maxDept = 0while s or p:while p:s.append(p)p = p.leftt = s[-1] if s else Noneif t.right and t.right != r:p = t.right  else:t = s.pop()r = tif not (t.left or t.right):t.dept = 1else:lDept = t.left.dept if t.left else 0rDept = t.right.dept if t.right else 0t.dept = max(lDept, rDept) + 1maxDept = max(maxDept, lDept+rDept+1)p = Nonereturn max(1, maxDept) -1