543-二叉树的直径

马谦马谦马谦

615
文章

17
评论

2018 年 12 月 5 日 12:21:19数据结构和算法评论279字数 773阅读 2 分 34 秒阅读模式

来源：力扣（LeetCode）

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

示例 :

给定二叉树

/ \

2 3

/ \

4 5

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

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

二、题解

本题最重要的一个点是要理清题意，求的是最大直径，是树内任意两点间的距离的最大值，不是求根节点到任意节点间距离的最大值（即深度）。

想法：

任意一条路径可以被写成两个箭头（不同方向），每个箭头代表一条从某些点向下遍历到孩子节点的路径。

假设我们知道对于每个节点最长箭头距离分别为 L,R，那么最优路径经过 L + R + 1 个节点。

算法：

按照常用方法计算一个节点的深度：max(depth of node.left, depth of node.right) + 1 。在计算的同时，经过这个节点的路径长度为 1 + (depth of node.left) + (depth of node.right) 。搜索每个节点并记录这些路径经过的点数最大值，期望长度是结果-1 。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        unsigned int diameter = 1;
        depth(root, diameter);
        return diameter - 1;
    }
private:
    int depth(TreeNode *node, unsigned int &diameter) {
        unsigned int lDepth, rDepth;
        if (node == NULL) {
            return 0;
        }
        lDepth = depth(node->left, diameter);
        rDepth = depth(node->right, diameter);

        diameter = max(diameter, lDepth + rDepth + 1);

        return max(lDepth, rDepth) + 1;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

int diameterOfBinaryTree(TreeNode* root) {

unsigned int diameter = 1;

depth(root, diameter);

return diameter - 1;

}

private:

int depth(TreeNode *node, unsigned int &diameter) {

unsigned int lDepth, rDepth;

if (node == NULL) {

return 0;

}

lDepth = depth(node->left, diameter);

rDepth = depth(node->right, diameter);

diameter = max(diameter, lDepth + rDepth + 1);

return max(lDepth, rDepth) + 1;

}

};

复杂度分析：

时间复杂度：O(N)，每个节点只访问一次。
空间复杂度：O(N)，深度优先搜索的栈开销。

2020-03-10 添加

为了完成 leetcode 每日 1 题打卡计划，使用 golang 重新提交了一次。

计算深度和直径的方式和上面略有不同，原理还是一样的：

func depth(root *TreeNode, diameter *int) int {
    if root == nil {
        return 0
    }

    // 左子节点的深度
    lDepth := depth(root.Left, diameter) + 1
    // 右子节点的深度
    rDepth := depth(root.Right, diameter) + 1

    // 当前节点的直径
    curDiameter := lDepth + rDepth - 1
    // 更新最大的直径
    if *diameter < curDiameter {
        *diameter = curDiameter
    }

    // 返回最大深度
    if lDepth < rDepth {
        return rDepth
    } else {
        return lDepth
    }
}

func diameterOfBinaryTree(root *TreeNode) int {
    var diameter int
    diameter = 0
    depth(root, &diameter)
    return diameter
}