本文首发于 语雀文档

题目

https://leetcode-cn.com/problems/diameter-of-binary-tree/

代码

  1. /**
  2. * Definition for a binary tree node.
  3. * function TreeNode(val, left, right) {
  4. *     this.val = (val===undefined ? 0 : val)
  5. *     this.left = (left===undefined ? null : left)
  6. *     this.right = (right===undefined ? null : right)
  7. * }
  8. */
  9. /**
  10. * @param {TreeNode} root
  11. * @return {number}
  12. */
  13. var diameterOfBinaryTree = function (root) {
  14.   if (root === null)
  15.     return 0
  16.   let res = 1
  17.   function traverse(root) {
  18.     if (root === null)
  19.       return 0
  20.     const left = traverse(root.left)
  21.     const right = traverse(root.right)
  22.     res = Math.max(res, left + right + 1)
  23.     return Math.max(left, right) + 1
  24.   }
  25.   traverse(root)
  26.   return res - 1
  27. };

反思

好久没刷了，这次刷回这题竟然又忘记了。

刷这题的时候，脑子里总有一个想法阻碍了我的思考，那就是：我该如何比较某一节点与其上层节点（或根节点）的路径长度大小。
但其实不应该这么想，我们应该把问题分解圈定在一个节点内（也就是动态规划 ，拆分问题）并简单化，所以正解应该是：对于一个节点，它的最大路径长度是多少，那肯定是左子节点长度+右子节点长度+当前节点，如果想知道哪个节点的路径长度最大，那就定义个变量专门存比较后的大小便是了。