Maximum Depth of BT(Binary Tree)

Given a binary tree, find height of it. Height of empty tree is -1, height of tree with one node is 0 and height of below tree is 2.

( root node 는 0으로 카운트해서 -1을 해주는 거군요. 그래서 아래의 tree 의  depth 는 2임 ! )

maxDepth() 의 pseudo code detail 을 한번 살펴보자.

거꾸로다 거꾸로! 아래의 4,5번부터 count 한다.

4,5는 자식이 없으니 0, 2는 자식(4,5) 이 있으니 1, 1은 2,3이라는 자식이 있으니 2가된다. 

maxDepth()
1. If tree is empty then return -1.
2. Else ! 
   ( a ) Get the max depth of left subtree recursively . ( call maxDepth( tree->left-subtree )
   ( b ) Get the max depth of right subtree recursively. ( call maxDepth( tree->right-subtree )
   ( c ) Get the max depths of left & right subtrees and add 1 to it for the current node.
        max_depth = max(max depth of left-sub, max depth of right-sub) + 1;
   ( d ) Return max_depth. !

class node
{
    public:
    int data;
    node* left;
    node* right;
};

int maxDepth(node* node)
{
    if(node == NULL) return -1;
    else {
        int l_Depth = maxDepth(node->left);
        int r_Depth = maxDepth(node->right);
                
        if(l_Depth > r_Depth) return (l_Depth+1);
        else return (r_Depth + 1);
    }
}


node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return (Node);
}

int main()
{
    node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    cout << "Height of tree is " << maxDepth(root) << '\n';
    
    return 0;
}

 

# Solution 

먼저 left노드의 끝으로 가서, left/right 을 다 한번씩 들린다. 

null 이니까 -1. 그리고 부모 값인 2로 가서 다시 right 인 5를 들리고, 5의 left / right 를 다 들린다. 물론 null 이니 -1. 

다시 부모인 2로 돌아가면 0 + 1 이니 1이다. 그리고 2의 부모인 1로 가서, 3을 간다. 근데 3의 자식이 없으니 0 + 1인 1. 

그리고 1로 돌아가면 1 + 1 이 되어서 2가 된다. 

 

# 관련 문제 

https://ding-dong-in-future.tistory.com/384

104. Maximum Depth of Binary Tree