LouisTsang-jk.github.io

二叉树的直径

出处

leetcode｜二叉树的直径

难度:简单

题解/思路

递归

• 空间复杂度 O(1)
• 时间复杂度 O(H) 这题要注意 ans 要和上次 ans 作比较，然后最终结果需要-1.

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var diameterOfBinaryTree = function(root) {
let ans = 1;
function depth (node) {
  if (!node) return 0;
  const L = depth(node.left);
  const R = depth(node.right);
  ans = Math.max(ans, L + R + 1);
  return Math.max(L, R) + 1;
}
depth(root);
return ans - 1;
};