[Binary Tree][Easy] 104. Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/description

Maximum Depth of Binary Tree - LeetCode

 

 

Q. 입력된 이진트리의 최대 depth를 구하라. 

 

Solution. 

  depth를 구하는 경우는 깊이 우선 탐색을 통하는 경우와, 너비 우선 탐색을 통한 

 두가지 경우를 다 생각해 볼수 있다. 

 두 가지 다 크게 어렵지 않은 접근으로, 알아 둬야 할 필요가 있겠다. 

 

 깊이 우선 탐색.

int maxDepthHelper(TreeNode* node, int depth)
{
    if (node == NULL)	return depth;
    ++depth;

    int leftD = maxDepthHelper(node->left, depth);
    int rightD = maxDepthHelper(node->right, depth);

    return max(leftD, rightD);
}
int maxDepth(TreeNode* root)
{
    int ret = maxDepthHelper(root, 0);
    return ret;
}

 

 

너비 우선 탐색

int maxDepth(TreeNode* root)
{
    if (root == NULL)	return 0;
    
    queue<TreeNode*> qBuff;
    qBuff.push(root);
    int ret = 0;
    while (!qBuff.empty())
    {
        int cnt = qBuff.size();
        for (int k = 0; k < cnt; ++k)
        {
            TreeNode* cur = qBuff.front();
            qBuff.pop();

            if (cur->left != NULL)	qBuff.push(cur->left);
            if (cur->right != NULL)	qBuff.push(cur->right);
        }
        ++ret;
    }
    return ret;
}