LeetCode 543：巧解二叉树直径问题

LeetCode543给你一棵二叉树的根节点返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点root。两节点之间路径的长度由它们之间边数表示。示例输入root [1,2,3,4,5]输出3解释3 取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。Python解法# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: max_len 0 def dfs(node): nonlocal max_len if not node: return 0 left_depth dfs(node.left) right_depth dfs(node.right) max_len max(max_len, left_depth right_depth) return max(left_depth, right_depth) 1 dfs(root) return max_lenJava解法class Solution { int max 0; public int diameterOfBinaryTree(TreeNode root) { dfs(root); return max; } int dfs(TreeNode node) { if(node null) return 0; int left dfs(node.left); int right dfs(node.right); max Math.max(max, left right); return Math.max(left, right) 1; } }C解法class Solution { public: int max_len 0; int diameterOfBinaryTree(TreeNode* root) { dfs(root); return max_len; } int dfs(TreeNode* node) { if(!node) return 0; int left dfs(node-left); int right dfs(node-right); max_len max(max_len, left right); return max(left, right) 1; } };