leetcode-543:二叉树的直径

简介: leetcode-543:二叉树的直径

题目

题目连接

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

示例 :

给定二叉树

1
     / \
    2   3
   / \     
  4   5    

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

解题

方法一:后续遍历(递归)

class Solution {
public:
    int res=0;
    int dfs(TreeNode* cur){//记录从该节点开始到叶子节点路径的最多节点数量
        if(!cur) return 0;
        if(!(cur->left||cur->right)) return 1;
        int l=dfs(cur->left);
        int r=dfs(cur->right);
        res=max(res,l+r);//更新结果
        return max(l,r)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return res;
    }
};
相关文章
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
54 6
|
28天前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
18 2
|
28天前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
15 2
|
28天前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
13 2
|
28天前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
15 0
|
28天前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
13 0
|
28天前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
12 0
|
28天前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
11 0
|
28天前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
13 0
|
3月前
|
存储 算法
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题