diameter-of-binary-tree

Diameter of Binary Tree – LeetCode 543

Problem

Description

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Answer

Original

Code

/**
 * 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 {
private:
    int Max = 0;
    
    int Msize(TreeNode* root){
        if(root){
            int l = Msize(root->left);
            int r = Msize(root->right);
            Max = max(Max, l + r);
            return 1 + max(l, r);
        } else {
            return 0;
        }
    }
    
public:
    int diameterOfBinaryTree(TreeNode* root) {
        Msize(root);
        return Max;
    }
};

思路

考虑到求得是书中任意两点距离的最大值，那么在跨跟节点时定然距离最大。同时也要考虑到因为跟节点单边不得不在单边的情况，但是这种情况往往会出现单边中的子跟节点并且情况重叠。于是都可以分割成子树的跨跟节点方案。那么最大值定来自与两跟的最大深度之和。于是就得到了一遍求最大深度一边取最大值的方案。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$4$ ms，排名$0\%$

Better

思路

还没看到更好的思路。