【leetcode_easy】543. Diameter of Binary Tree
2024-09-05 05:51:03
problem
题意:
转换一种角度来看,是不是其实就是根结点1的左右两个子树的深度之和呢。那么我们只要对每一个结点求出其左右子树深度之和,这个值作为一个候选值,然后再对左右子结点分别调用求直径对递归函数,这三个值相互比较,取最大的值更新结果res,因为直径不一定会经过根结点,所以才要对左右子结点再分别算一次。为了减少重复计算,我们用哈希表建立每个结点和其深度之间的映射,这样某个结点的深度之前计算过了,就不用再次计算了。
solution1: 两个递归函数。
/**
* 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) {
if(root==NULL) return ;
int ans = getHeight(root->left) + getHeight(root->right);
return max(ans, max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
}
int getHeight(TreeNode* node)
{
if(node==NULL) return ;
if(mymap.count(node)) return mymap[node];
int h = + max(getHeight(node->left), getHeight(node->right));
mymap[node] = h;
return h;
}
private:
unordered_map<TreeNode*, int> mymap;
};
solution2: 一个递归函数。
只需要用一个递归函数就可以了,可以在求深度的递归函数中顺便就把直径算出来,而且貌似不用进行优化也能accept。
solution3:
优化版本。
参考
1. Leetcode_easy_543. Diameter of Binary Tree;
2. Grandyang;
完
最新文章
- [导读]Learning from Imbalanced Classes
- linux不知道文件在哪,想查找文件内的字符串
- Area区域
- C#多线程之旅(1)——介绍和基本概念
- linux建立ssh信任关系
- SQL基础篇---函数及其函数配套使用的关键字
- c++ std::string 用法
- easyui源码翻译1.32--EasyLoader(简单加载)
- Appium Server 传递Android参数
- wc的用法
- linux下ssh端口的修改和登录
- sqoop实现关系型数据库与hadoop之间的数据传递-import篇
- [51nod1614]刷题计划
- 20162330 实验二 《Java面向对象程序设计》 实验报告
- APP界面设计与页面布局的23条基本原则
- CF1119A Ilya and a Colorful Walk
- c语言小项目---通讯录2.0
- jdk各版本特性
- MySQL SELECT 执行的具体步骤
- Codeforces Round 500 (Div 2) Solution
热门文章
- 《流畅的Python》Object References, Mutability, and Recycling--第8章
- rabbitmq 配置多个消费者(转载)
- linux实操_shell系统函数
- 算法:统计1-n中,1出现的次数
- python的变量命名规范
- BZOJ 5494: [2019省队联测]春节十二响 (左偏树 可并堆)
- Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 1) 题解
- Github:VS使用GitHub要点
- JMeter性能测试工具
- 基于Kinect 2.0深度摄像头的三维重建