leetcodeのeasyだけどeasyじゃなかった問題1

543. Diameter of Binary Tree

2分木の直径（左右ノードが最長となるときの長さ）を求める問題です。

この問題はノードの高さを求めるアルゴリズムを知ってる前提だと確かに簡単なのですが、知らないとそこから考えないといけないのでちょっと大変です。

前提としてのノードの高さの求め方

左右のノードの高いほうに１を足すとノードの高さになるというのを再帰的に行うとノードの高さが求められます。

int tree_height(Node* root) {
    if (root == NULL) 
        return 0;
    else {
        int left_height = tree_height(root->left);
        int right_height = tree_height(root->right);
         
        return max(left_height, right_height) + 1;
}

２分木の直径

簡単な方法

全てのノードで左右の高さを計算し最大のものを求める方法です。

ただこれだと無駄に計算量がかかってしまいます。O(N²)

class Solution {
public:
    int diameter = 0;
    
    int diameterOfBinaryTree(TreeNode* root) {
        traverse(root);
        return diameter;
    }
    
    // 全てのノードを探索
    void traverse(TreeNode* root) {
        if (root == NULL) return;
        
        int left_height = tree_height(root->left);
        int right_height = tree_height(root->right);
        diameter = max(diameter, left_height + right_height);
        
        traverse(root->left);
        traverse(root->right);
    }
    
    // ノードの高さを取得
    int tree_height(TreeNode* root) {
        if (root == NULL) 
            return 0;
        else {
            int left_height = tree_height(root->left);
            int right_height = tree_height(root->right);
         
            return max(left_height, right_height) + 1;
        }
    }
};

最適な方法

ノードの高さを求めるアルゴリズムの途中で最大値を求めてしまえばO(N)で求めることができます。

class Solution {
public:
    int diameter = 0;
    
    int diameterOfBinaryTree(TreeNode* root) {
        tree_height(root);
        return diameter;
    }
    
    int tree_height(TreeNode* root) {
        if (root == NULL) 
            return 0;
        else {
            int left_height = tree_height(root->left);
            int right_height = tree_height(root->right);
            
            // 左右が最大になるものを記録
            diameter = max(diameter, left_height + right_height);
         
            return max(left_height, right_height) + 1;
        }
    }
};