木又连续日更第98天(98/100)
木又的第142篇leetcode解题报告
二叉树
类型第32篇解题报告
leetcode第543题:二叉树的直径
https://leetcode-cn.com/problems/diameter-of-binary-tree/
【题目】
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意:两结点之间的路径长度是以它们之间边的数目表示。
【思路】
递归遍历,得到节点左右子树的最大高度left和right,那么通过该节点的最大路径长度是left+right-2。(注意:本题的路径长度,不是顶点个数,而是边的个数)
【代码】
python版本
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
self.max_length = 0
self.get_max_depth(root)
return self.max_length
def get_max_depth(self, node):
if not node:
return 0
left = self.get_max_depth(node.left) + 1
right = self.get_max_depth(node.right) + 1
self.max_length = max(self.max_length, left+right-2)
print(node.val, left, right)
return max(left, right)
C++版本
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int res = 0;
if(!root)
return res;
get_max_depth(root, res);
return res;
}
int get_max_depth(TreeNode* node, int& res){
if(!node)
return 0;
int left = get_max_depth(node->left, res) + 1;
int right = get_max_depth(node->right, res) + 1;
res = max(res, left+right-2);
return max(left, right);
}
};