题目大意 https://leetcode-cn.com/problems/diameter-of-binary-tree/description/ 给定一棵二叉树，你需要计算它的直径长度。...一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。...解题思路 二叉树的直径：二叉树中从一个结点到另一个节点最长的路径，叫做二叉树的直径 采用分治和递归的思想：根节点为root的二叉树的直径 = max(root-left的直径，root->right的直径...，root->left的最大深度+root->right的最大深度+1) 分两种情况，1，最大直径经过根节点，则直径为左子树最大深度+右子树最大深度 2.如果不经过根节点，则取左子树或右子树的最大深度
二叉树直径的定义：二叉树中路径的最大长度 二叉树中路径的最大长度，可以理解所有节点的左右子树高度之和的最大值。...假设二叉树有n个节点，编号为{a1,a2,…,an}, 其对应的左右子树的高度之和为H = {h1,h2,h3,…,hn}, 则该二叉树的直径为max(H)。...struct node { int val; node *left, *right; }; int ans = 0;// 用于维护任意节点左右子树高度和的最大值 //dfs()函数的返回值是当前节点的高度
# LeetCode-543-二叉树的直径 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。...示例1： 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3...**注意：**两结点之间的路径长度是以它们之间边的数目表示。 # 解题思路 方法1、DFS： 二叉树的直径是不一定经过root节点的，可能存在于每个子树中，所以需要遍历每个节点的左右子树深度。...动态记录最大的直径 直径 = max(左子树深度+右子树深度) 某节点子树的深度 = max(某节点左子树深度，某节点右子树深度)+1 # Java代码 /** * Definition for a
之前也写过不少关于二叉树的东西了，但是总体来说，二叉树还是一个很绕的东西，所以单独择出来写一篇笔记，之前也没计划什么的，就想到什么写什么吧。...不过该篇文章的主要内容是关于二叉树的三种遍历（前序、中序、后序）不同的实现方式（递归与非递归）。 首先，我觉得很有必要去彻底理解一下递归。...个人认为，可以用循环实现的，递归基本上都可以实现，但有时递归的效率不如循环。 （3）递归又分为单递归与多递归（二叉树的三种遍历递归方法均用到了双递归！）...二叉树的三种遍历：前序（根左右）、中序（左根右）、后序（左右根） ? 首先看三种遍历的递归实现方法。...上述三个方法均存在一个打印，两个递归，但是唯一的区别就是顺序的不同，所以，如何理解呢！！！
文章目录 1.问题描述 2.难度等级 3.热门指数 4.解题思路 参考文献 1.问题描述 给你一棵二叉树的根节点，返回该树的直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的长度 。...而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。...具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在 O(1) 时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。...时间复杂度： O(n)，其中 n 为二叉树的结点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次。 空间复杂度： 递归函数分配栈空间为 O(logn)，即二叉树的高度。...二叉树的直径- LeetCode
一 题目： 二 思路： 分析下，二叉树的最长路径某个结点的左孩子最大深度加右孩子的最大深度 我们只需要找出每一个节点的 左子树最大深度 + 右子树最大深度 的值，然后不断更新全局变量max 就行了...代码： class Solution { int max; public int diameterOfBinaryTree(TreeNode root) { //分析下，二叉树的最长路径某个结点的左孩子最大深度加右孩子的最大深度...max=0; dfs(root); return max; } /** * 返回树的深度 */ private...int dfs(TreeNode root) { if (root==null){ return 0; } //左子树的深度...int lDeep= dfs(root.left); //右子树的深度 int rDeep= dfs(root.right); max=Math.max
非递归的方法是用存储代替计算，就是在建立树时，实现了存储展开，相当于存储了未来需要遍历的路径，所以就快了。...递归是送快递，一层层往下递，非递归是先建好区域仓库，由各地仓库储存发货，所以速度更快，但需要仓库储存（内存占用更多）。...二叉树遍历在数据结构中用得多，这种算法是从kb时代的内存来的，主要用于理解概念，提升编程时的思想用。 实际用途中如果用于商业一般用数据库代替，根本用不到二叉树，是用存储代替计算。...速度快，可以用内存数据库，如我用h2 database的Memory Mode 在java下可以实现1秒1百万次插入。用sqlite内存模式代替以前在c++需要手工管理的数据结构。...当然如果你写加密算法，这种要求极高的程序时，还是需要考虑性能最大化的，否则一般用存储代替遍历计算，因为内存和硬盘，现在很便宜了，而cpu还是一种宝贵的资源。
可以将二叉树的直径转换为：二叉树的每个节点的左右子树的高度和的最大值。 ——leetcode此题热评 前言 哈喽，大家好，我是一条。 糊涂算法，难得糊涂 Question 543....二叉树的直径 难度：简单 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 示例 : ?...Solution 还是递归+深度优先搜索 我们定义一个递归函数 depth(node) ，函数返回该节点为根的子树的深度。...先递归调用左儿子和右儿子求得它们为根的子树的深度 L和 R，则该节点为根的子树的深度即为max(L,R)+1 递归搜索每个节点返回最大值即可。...(node.left); int Right = depth(node.right); maxd=Math.max(Left+Right,maxd);//将每个节点最大直径
题目 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。...示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3...注意：两结点之间的路径长度是以它们之间边的数目表示。...maxDiameter); int right = diameter(root->right,maxDiameter); int curMax = left+right;//包含当前根节点的直径为
📷 DFS解法 /** * Definition for a binary tree node. * struct TreeNode { * in...
一、题目 给你一棵二叉树的根节点，返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。...> 示例 2： 【输入】root = [1,2] 【输出】1 提示： 树中节点数目在范围 [1, 10^4] 内 -100 <= Node.val <= 100 三、解题思路 根据题目描述，我们要获得二叉树中任意两个节点的最大直径...的距离其实没有必要参与最大直径的计算，因为leftNode到rightNode的距离一定倾向是最大直径。...所以，我们得出一个结论： 可能的最大直径 = leftNode到rootNode的距离 + rootNode到rightNode的距离； 那么，因为二叉树也并不只有3个节点，如果节点很多的话，那么这个二叉树的层级也就会越深...那么针对树形结构的解题，最常用的方式就是递归算法了，从叶子节点开始统计，一直统计到根节点，并且每次都要进行直径的计算和比较，当遍历到根节点时，最大直径也就计算出来了。
二叉树的直径 - 力扣（LeetCode） 要找两个节点之间最多的边数，这个最多的边数必定是某个节点的左右子树的深度之和，因此递归计算每个子树的深度，过程中记录最大和即可 class Solution
今天和大家聊的问题叫做 二叉树的直径，我们先来看题面： https://leetcode-cn.com/problems/diameter-of-binary-tree/ Given the root...给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。...把所有节点作为根节点，比较所有根节点的最大路径长度，选最大的。...root->right); md = max(md, td); preOrder(root->left); preOrder(root->right); } }; 思路二：利用递归...，对每一个根节点，计算其左边的深度和右边的深度，左右深度相加即为当前子树的直径，遍历完每一棵子树后最大的那个直径即为二叉树的直径。
二 叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。...因为树的定义本身就是 递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。...在三种遍历中， 前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。 一.前序遍历 前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。 ...1.递归实现 void in_order(BTree* root) { //必不可少的条件,递归的出口 if(root !... 后序遍历的非递归实现是三种遍历方式中最难的一种。
简介 树中所有简单路径的最大值即为树的直径，可以通过两次 DFS 或者树形 DP 在 时间内求解。 2....证明 假设结点 和 之间唯一的简单路径为树的直径， 表示结点 和 之间的唯一的简单路径的长度。...若该最远点 不是树的直径的一个端点，则对于当前根结点 来说： 如果 或 二者有一个不与 在同一个子树（假设为 ），则由于 与 为直径而 不是直径的端点矛盾。...如果 均与 在同一个子树，易知树的直径 没有经过树根 。...推论：树中任意结点的最远点要么是 ，要么是 （ )为树的直径）。 证明同上，略。
求一棵树的直径的方法就是，从一个顶点出发，找到离它最远的顶点s，然后从顶点s出发，找离他最远的节点t.那么，s、t之间的距离就是树的直径。...对于加权无向树来说，树的直径就是s、t之间的路径上的边的权值相加。
二 叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。...因为树的定义本身就是 递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。...= NULL) q.push(p->rchild); } } 五.二叉树的其他一些应用 1.求二叉树的深度 若一棵二叉树为空，则它的深度为0，否则它的深度等于左子树和右子树中的最大深度加...设nLeft为左子树的深度，nRight为右子树的深度， 则二叉树的深度为：max(nLeft , nRight)+1....(nLeft + 1):(nRight + 1); } 2.从二叉树中查找值为x的结点。
文章目录 前言 问题描述 递归实现 非递归实现 参考文献 前言 二叉树翻转是一道经典的面试编程题，经常出现在各大公司的招聘笔试面试环节。...问题分析 翻转一个二叉树，直观上看，就是把二叉树的每一层左右顺序倒过来。...因此翻转一个二叉树，就是把根结点的左子树翻转一下，同样的把右子树翻转一下，在交换左右子树就可以了。 当然，翻转左子树和右子树的过程和当前翻转二叉树的过程没有区别，就是递归的调用当前的函数就可以了。...因此，翻转二叉树的步骤可总结如下： （1）交换根结点的左子结点与右子结点； （2）翻转根结点的左子树（递归调用当前函数）； （3）翻转根结点的右子树（递归调用当前函数）。...具体实现 // @brief: 非递归翻转二叉树 // @param: 二叉树根结点 // @ret: 翻转后的二叉树根结点 BinaryTreeNode* invertBTNonrecu(BinaryTreeNode
1.树的直径的求法不是很难，两遍DFS，树的直径又称为最长路，没看到树的直径的裸题，除了饭店的那个题，讲的是有一家饭店在一个图中，饭店的送餐时间与最远的送餐距离成正比，求饭店的修建位置使得饭店的送餐时间最短...，那么这个题就是说在图中赵找一条最长路，将饭店建在最长路的中心，这个题也是CCPC2019网络赛的一个题，几乎一样的模板，但是这个知识点常与树形DP一起出现，什么添边，什么附加条件，但是离不开最长路两边
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
