[leetcode] 543. Diameter of Binary Tree

[leetcode] 543. Diameter of Binary Tree

Description

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example: Given a binary tree

1 / \ 2 3 / \ 4 5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

分析

题目的意思是：求一个二叉树最长的路径长度，起点不一定是根节点。

思路是我们在递归的时候，只需要选择选择当前结点分支的最大长度返回就行了，即max(left,right)+1；当然，res就是左右分支的和了。

代码

/** * 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 {private: int res=0;public: int diameterOfBinaryTree(TreeNode* root) { maxDepth(root); return res; } int maxDepth(TreeNode* root){ if(!root){ return 0; } int left=maxDepth(root->left); int right=maxDepth(root->right); res=max(res,left+right); return max(left,right)+1; }};

代码二

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def maxDepth(self,root): if(root is None): return 0 l=self.maxDepth(root.left) r=self.maxDepth(root.right) self.ans=max(self.ans,l+r+1) return max(l,r)+1 def diameterOfBinaryTree(self, root: TreeNode) -> int: self.ans=1 self.maxDepth(root) return self.ans-1

参考文献

​​LeetCode 543. Diameter of Binary Tree 解题笔记​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。