LeetCode543二叉树的直径

Posted on | | Visitors:
Words count in article: 405 字 | Reading time ≈ 2 分

题目链接

https://leetcode-cn.com/problems/diameter-of-binary-tree/

题解

  • 一棵二叉树的直径长度是任意两个结点路径长度中的最大值，两结点之间的路径长度是以它们之间边的数目表示
  • 将一条路径分为左右两半，两个结点之间路径长度等于根结点左右子树的深度之和
  • 这条路径可能穿过也可能不穿过根结点，所以在DFS过程中记录路径长度的最大值
  • 相似的题目有
  • 要注意depth函数的功能
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Problem: LeetCode 543
// URL: https://leetcode-cn.com/problems/maxDiameter-of-binary-tree/
// Tags: Tree DFS Recursion
// Difficulty: Easy

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode{
    TreeNode* left;
    TreeNode* right;
    int val;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

class Solution{
private:
    int maxDiameter=0;  // 全局最大直径

    // 返回该树的最大深度
    int depth(TreeNode* root){
        // 空结点深度为0
        if(root==nullptr)
            return 0;
        // 左右子树深度
        int leftDepth = depth(root->left);
        int rightDepth = depth(root->right);
        // 更新最大直径：两个结点之间路径长度等于根结点左右子树的深度之和
        if (leftDepth + rightDepth > this->maxDiameter)
            this->maxDiameter = leftDepth + rightDepth;
        // 返回该树最大深度
        return max(leftDepth, rightDepth) + 1;
    }

public:
    // 求一颗树的直径：任意两个结点路径长度中的最大值
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return this->maxDiameter;
    }
};

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!