二叉树的直径二叉树的直径

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

1 / \ 23 / \ 45

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
思路：

求最大直径 == 求（经过最多的节点数 - 1）；

最多的节点数 == 以任意节点出发，从左右子节点遍历的路径数拼接（左子树节点数 + 右子树节点数 + 1 [该节点] ）。至此，原问题分成左右子树路径长度这两个子问题；

用D_node表示以node为起点经过的节点数的最大值，则直径为所以节点D_node中取最大值 - 1；

计算D_node使用递归函数。

以下代码来源于Leetcode官方

Python版：

class Solution(object): def diameterOfBinaryTree(self, root): self.ans = 1# ans用来record最大值 def depth(node): # 访问到空节点了，返回0 if not node: return 0 # 左儿子为根的子树的深度 L = depth(node.left) # 右儿子为根的子树的深度 R = depth(node.right) # 计算d_node即L+R+1 并更新ans self.ans = max(self.ans, L+R+1) # 返回该节点为根的子树的深度 return max(L, R) + 1depth(root) return self.ans - 1

C++版：

class Solution { int ans; int depth(TreeNode* rt){ if (rt == NULL) return 0; // 访问到空节点了，返回0 int L = depth(rt->left); // 左儿子为根的子树的深度 int R = depth(rt->right); // 右儿子为根的子树的深度 ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans return max(L, R) + 1; // 返回该节点为根的子树的深度 } public: int diameterOfBinaryTree(TreeNode* root) { ans = 1; depth(root); return ans - 1; } };

C++里建立二叉树用Treenode类型

Java版：

class Solution { int ans; public int diameterOfBinaryTree(TreeNode root) { ans = 1; depth(root); return ans - 1; } public int depth(TreeNode node) { if (node == null) return 0; // 访问到空节点了，返回0 int L = depth(node.left); // 左儿子为根的子树的深度 int R = depth(node.right); // 右儿子为根的子树的深度 ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ans return Math.max(L, R) + 1; // 返回该节点为根的子树的深度 } }