二叉树的直径

[编程题]二叉树的直径

热度指数：2783 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一颗二叉树，求二叉树的直径。

1.该题的直径定义为：树上任意两个节点路径长度的最大值

2.该题路径长度定义为：不需要从根节点开始，也不需要在叶子节点结束，也不需要必须从父节点到子节点，一个节点到底另外一个节点走的边的数目

3.这个路径可能穿过根节点，也可能不穿过

4.树为空时，返回 0

如，输入{1,2,3,#,#,4,5}，二叉树如下:

那么：

从4到5的路径为4=>3=>5，路径长度为2

从4到2的路径为4=>3=>1=>2，路径长度为3

如，输入{1,2,3,#,#,4,5,9,#,#,6,#,7,#,8}，二叉树如下:

那么路径长度最长为:7=>9=>4=>3=>5=>6=>8，长度为6

数据范围：节点数量满足 $0 \le n \le 100 \$

示例1

输入

{1,2,3,#,#,4,5}

输出

示例2

输入

{1,2,3,#,#,4,5,9,#,#,6,#,7,#,8}

输出

示例3

输入

{1,2,3}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

猪猪侠新新酱

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型
 */
 //以 root 为头结点的树，最大直径就是左右两个子树的高度相加 
 int dfs(struct TreeNode* root){
    if(NULL==root)
       return 0;
    else{
        return (dfs(root->left)>dfs(root->right)?dfs(root->left):dfs(root->right))+1;
    }
 }
int diameterOfBinaryTree(struct TreeNode* root ) {
    // write code here
    if(root==NULL)
      return NULL;
    return dfs(root->left)+dfs(root->right);
}

发表于 2023-01-10 23:01:19 回复(0)