[C++][leetcode] Diameter of Binary Tree :: seoftware

 

---

 

소스코드

 

---

 

/**
 * 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 {
    int max;
    void maxDepth(TreeNode* root) {
        if (root == NULL) {
            return;
        }
        max = std::max(max, height(root->left) + height(root->right));
        maxDepth(root->left);
        maxDepth(root->right);
    }
    
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        return 1 + std::max(height(root->left), height(root->right));
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        max = 0;
        maxDepth(root);
        return max;
    }
};

 

1. maxDepth(TreeNode *root) : root를 꺾는 노드(예제에서는 1)을 하여 최댓값을 구한다.

 

2. height(TreeNode * root) : root로부터 leaf node 까지의 길이를 구한다.