算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！今天和大家聊的问题叫做 二叉树的直径，我们先来看题面：https:///problems/diameter-of-binary-tree/Given the root of a binary tree, return 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. The length of a path between two nodes is represented by the number of edges between them.
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。示例 解题思路一：不一定最长路径一定要穿过根节点，所以每个节点都要遍历，把每个节点作为根节点，然后，算出根节点左子树的最大深度和右子树的最大深度，把把左右子树的最大深度加起来，作为暂时当前根节点的最大路径长度。把所有节点作为根节点，比较所有根节点的最大路径长度，选最大的。class Solution {
public:
int md, td;
int diameterOfBinaryTree(TreeNode* root) {
if (!root)
return 0;
md = td = 0;
preOrder(root);
return md;
}
int maxDepth(TreeNode *root)//计算每个节点（根节点）的左右子树最大深度
{
if (!root)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
else if (!root->left)
return maxDepth(root->right)+1;
else if (!root->right)
return maxDepth(root->left)+1;
else
return max(maxDepth(root->left), maxDepth(root->right))+1;
}
void preOrder(TreeNode *root)//遍历每个节点，把遍历到的每个节点作为根节点
{
if (!root)
return;
td= maxDepth(root->left) + maxDepth(root->right);
md = max(md, td);
preOrder(root->left);
preOrder(root->right);
}
};
思路二：利用递归，对每一个根节点，计算其左边的深度和右边的深度，左右深度相加即为当前子树的直径，遍历完每一棵子树后最大的那个直径即为二叉树的直径。class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int res=0;
depth(root,res);
return res;
}
private:
int depth(TreeNode *root,int &res){
if (!root) return 0;
int left_depth=depth(root->left,res);
int right_depth=depth(root->right,res);
res=max(res,right_depth+left_depth);
return max(left_depth+1,right_depth+1);
}
};
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
|
