LeetCode 543 Diameter of Binary Tree

标签: 二叉树 LeetCode 发布于:2022-02-06 16:57:43 编辑于:2022-02-06 16:57:50 浏览量:913

概述

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

后续遍历

借求最大深度时计算通过该节点的最大路径长度。

要注意的是,路径长度为路径上节点个数减一,即 d = leftMaxDepth + rightMaxDepth + 1 - 1

class Solution {
public:
    int maxD = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        maxDepth(root);
        return maxD;
    }
    
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        int ld = maxDepth(root->left);
        int rd = maxDepth(root->right);
        int d = ld + rd;
        maxD = max(maxD, d);
        return max(ld, rd) + 1;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/