C++ LeetCode543题解二叉树直径

目录
  • LeetCode 543.二叉树的直径
  • 方法一：深度优先搜索求二叉树的深度
  • AC代码
    • C++

LeetCode 543.二叉树的直径

力扣题目链接：leetcode.cn/problems/di…

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :给定二叉树

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

方法一：深度优先搜索求二叉树的深度

我们只需要求出每个节点的左子树的最大深度，以及右子树的最大深度。

AC代码

C++

class Solution {
private:
    int ans;
    int getDeepth(TreeNode* root) {
        if (!root)
            return 0;
        int left = getDeepth(root->left);
        int right = getDeepth(root->right);
        ans = max(ans, left + right);
        return max(left, right) + 1;
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0;
        getDeepth(root);
        return ans;
    }
};

以上就是C++ LeetCode543题解二叉树直径的详细内容，更多关于C++ 二叉树直径的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C++ LeetCode1775通过最少操作次数使数组和相等

    目录 LeetCode1775.通过最少操作次数使数组的和相等 方法一:贪心 + 计数 AC代码 C++ LeetCode1775.通过最少操作次数使数组的和相等 力扣题目链接:leetcode.cn/problems/eq… 给你两个长度可能不等的整数数组 nums1 和 nums2 .两个数组中的所有值都在 1 到 6 之间(包含 1 和 6). 每次操作中,你可以选择 任意 数组中的任意一个整数,将它变成 1 到 6 之间 任意 的值(包含 1 和 6). 请你返回使 nums1 中所有数

  • C++ LeetCode1832题解判断句子是否为全字母句

    目录 LeetCode 1832.判断句子是否为全字母句 方法一:统计 AC代码 C++ LeetCode 1832.判断句子是否为全字母句 力扣题目链接:leetcode.cn/problems/ch… 全字母句 指包含英语字母表中每个字母至少一次的句子. 给你一个仅由小写英文字母组成的字符串 sentence ,请你判断 sentence 是否为 全字母句 . 如果是,返回 true :否则,返回 false . 示例 1: 输入:sentence = "thequickbrownfoxju

  • C++ LeetCode1781题解所有子字符串美丽值之和

    目录 LeetCode 1781.所有子字符串美丽值之和 方法一:前缀和 AC代码 C++ 方法二:边遍历边计算 AC代码 C++ LeetCode 1781.所有子字符串美丽值之和 力扣题目链接:leetcode.cn/problems/su… 一个字符串的 美丽值 定义为:出现频率最高字符与出现频率最低字符的出现次数之差. 比方说,"abaacc" 的美丽值为 3 - 1 = 2 . 给你一个字符串 s ,请你返回它所有子字符串的 美丽值 之和. 示例 1: 输入:s = &quo

  • C++ LeetCode1780判断数字是否可以表示成三的幂的和

    目录 LeetCode 1780.判断一个数字是否可以表示成三的幂的和 方法一:二进制枚举 题目分析 解题思路 复杂度分析 AC代码 C++ 方法二:进制转换 AC代码 C++ LeetCode 1780.判断一个数字是否可以表示成三的幂的和 力扣题目链接:leetcode.cn/problems/ch… 给你一个整数 n ,如果你可以将 n 表示成若干个不同的三的幂之和,请你返回 true ,否则请返回 false . 对于一个整数 y ,如果存在整数 x 满足 y == 3x ,我们称这个整

  • C++ LeetCode1805字符串不同整数数目

    目录 LeetCode 1805.字符串中不同整数的数目 方法一:遍历拆分 AC代码 C++ LeetCode 1805.字符串中不同整数的数目 力扣题目链接:leetcode.cn/problems/nu… 给你一个字符串 word ,该字符串由数字和小写英文字母组成. 请你用空格替换每个不是数字的字符.例如,"a123bc34d8ef34" 将会变成 " 123  34 8  34" .注意,剩下的这些整数为(相邻彼此至少有一个空格隔开):"123&q

  • C++ LeetCode1812判断国际象棋棋盘格子颜色

    目录 1812.判断国际象棋棋盘中一个格子的颜色 方法一:取模 AC代码 C++ 方法二:基于方法一的小改进 AC代码 C++ 1812.判断国际象棋棋盘中一个格子的颜色 力扣题目链接:leetcode.cn/problems/de… 给你一个坐标 coordinates ,它是一个字符串,表示国际象棋棋盘中一个格子的坐标.下图是国际象棋棋盘示意图. 如果所给格子的颜色是白色,请你返回 true,如果是黑色,请返回 false . 给定坐标一定代表国际象棋棋盘上一个存在的格子.坐标第一个字符是字

  • C++ LeetCode300最长递增子序列

    目录 LeetCode 300.最长递增子序列 方法一:动态规划 AC代码 C++ LeetCode 300.最长递增子序列 力扣题目链接:leetcode.cn/problems/lo… 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度. 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序.例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列. 示例 1: 输入:nums = [10,9,2,5,3,7,101,18]输出:4

  • C++ LeetCode1827题解最少操作使数组递增

    目录 LeetCode1827.最少操作使数组递增 方法一:遍历 AC代码 C++ LeetCode1827.最少操作使数组递增 力扣题目链接:leetcode.cn/problems/mi… 给你一个整数数组 nums (下标从 0 开始).每一次操作中,你可以选择数组中一个元素,并将它增加 1 . 比方说,如果 nums = [1,2,3] ,你可以选择增加 nums[1] 得到 nums = [1,3,3] . 请你返回使 nums 严格递增 的 最少 操作次数. 我们称数组 nums 是

  • C++ LeetCode543题解二叉树直径

    目录 LeetCode 543.二叉树的直径 方法一:深度优先搜索求二叉树的深度 AC代码 C++ LeetCode 543.二叉树的直径 力扣题目链接:leetcode.cn/problems/di… 给定一棵二叉树,你需要计算它的直径长度.一棵二叉树的直径长度是任意两个结点路径长度中的最大值.这条路径可能穿过也可能不穿过根结点. 示例 :给定二叉树 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]. 注意:两结点之间的路径长度是以它们之间边的数目表示. 方法一:深度优

  • go语言算法题解二叉树的最小深度

    目录 题目: 说明: 解法: 题目: 给定一个二叉树,找出其最小深度. 最小深度是从根节点到最近叶子节点的最短路径上的节点数量. 说明: 叶子节点是指没有子节点的节点. 解法: func minDepth(root *TreeNode) int { if root == nil { return 0 } minDepth := math.MaxInt64 var dfs func(node *TreeNode, depth int) dfs = func(node *TreeNode, dept

  • C++二叉树的直径与合并详解

    C++二叉树的直径与合并详解

    目录 二叉树的直径 给定一棵二叉树,你需要计算它的直径长度.一棵二叉树的直径长度是任意两个结点路径长度中的最大值.这条路径可能穿过也可能不穿过根结点. 思路 合并二叉树 给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠.你需要将他们合并为一个新的二叉树.合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点. 思路 1.确定递归函数的参数和返回值: 2.确定终止条件: 3.确定单层递归的逻辑:

  • C C++ LeetCode题解在二叉树中增加一行示例详解

    C C++ LeetCode题解在二叉树中增加一行示例详解

    目录 题目描述 整理题意 解题思路分析 层序遍历(广度优先搜索) 递归(深度优先搜索) 具体实现 复杂度分析 代码实现 层序遍历(广度优先搜索) 递归(深度优先搜索) 总结 题目描述 题目链接:623. 在二叉树中增加一行 给定一个二叉树的根 root 和两个整数 val 和 depth ,在给定的深度 depth 处添加一个值为 val 的节点行. 注意,根节点 root 位于深度 1 . 加法规则如下: 给定整数 depth,对于深度为 depth - 1 的每个非空树节点 cur ,创建两

  • java面试题解LeetCode27二叉树的镜像实例

    目录 正文 解题思路 方法一:递归法 方法二:辅助栈(或队列) 正文 LeetCode27. 二叉树的镜像 请完成一个函数,输入一个二叉树,该函数输出它的镜像. 例如输入: 4 /2 7 / \ /1 3 6 9 镜像输出: 4 /7 2 / \ /9 6 3 1 示例 1: 输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 限制: 0 <= 节点个数 <= 1000 解题思路 方法一:递归法 根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个

  • 前端算法题解leetcode114二叉树展开为链表

    前端算法题解leetcode114二叉树展开为链表

    目录 正文 解题思路-基础 代码实现 解题思路-进阶 代码实现 正文 题目地址 给你二叉树的根结点 root ,请你将它展开为一个单链表: 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null . 展开后的单链表应该与二叉树 先序遍历 顺序相同. 示例 1: 输入: root = [1,2,5,3,4,null,6]输出: [1,null,2,null,3,null,4,null,5,null,6] 示例 2: 输入: root

  • PHP实现判断二叉树是否对称的方法

    本文实例讲述了PHP实现判断二叉树是否对称的方法.分享给大家供大家参考,具体如下: 问题 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的. 题解 递归判断二叉树两侧. 实现代码: <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ func

  • 二叉树递归迭代及morris层序前中后序遍历详解

    二叉树递归迭代及morris层序前中后序遍历详解

    目录 分析二叉树的前序,中序,后序的遍历步骤 1.层序遍历 方法一:广度优先搜索 方法二:递归 2.前序遍历 3.中序遍历 4.后序遍历 递归解法 前序遍历--递归 迭代解法 前序遍历--迭代 核心思想: 三种迭代解法的总结: Morris遍历 morris--前序遍历 morris--中序遍历 morris--后序遍历: 分析二叉树的前序,中序,后序的遍历步骤 1.层序遍历 方法一:广度优先搜索   (以下解释来自leetcode官方题解) 我们可以用广度优先搜索解决这个问题. 我们可以想到最

  • JavaScript实现二叉树的先序、中序及后序遍历方法详解

    本文实例讲述了JavaScript实现二叉树的先序.中序及后序遍历方法.分享给大家供大家参考,具体如下: 之前学数据结构的时候,学了二叉树的先序.中序.后序遍历的方法,并用C语言实现了,下文是用js实现二叉树的3种遍历,并以动画的形式展现出遍历的过程. 整个遍历过程还是采用递归的思想,原理很粗暴也很简单 先序遍历的函数: function preOrder(node){ if(!(node==null)){ divList.push(node); preOrder(node.firstEleme

  • Python探索之创建二叉树

    问题 创建一个二叉树 二叉树有限多个节点的集合,这个集合可能是: 空集 由一个根节点,和两棵互不相交的,分别称作左子树和右子树的二叉树组成 创建二叉树,创建节点,再创建节点之间的关系 Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 class TreeNode(object): def __init__ (self, data, left = None, right

随机推荐