두 갈래 나무 시리즈 - 두 갈래 나무의 깊이, 예 [LeetCode]

두 갈래 나무의 깊이라는 개념이 가장 주목할 만한 것은'잎'노드까지의 거리에 있다.
일반적으로'깊이'라고 직접적으로 말하면 모두 최대 깊이, 즉 가장 먼 잎의 거리를 가리킨다.
 
여기에 두 개의 예제를 놓아라. 최소 깊이와 최대 깊이.

1. 두 갈래 나무의 최소 깊이

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int minDepth(TreeNode *root) {
13     }
14 };

 
깊이는 반드시 잎 노드까지의 거리이기 때문에 깊이를 사용하여 반복할 때 단순히 좌우 나무의 귀환 결과를 비교하여 작은 값을 되돌릴 수 없다. 왜냐하면 한 아이가 비어 있는 노드에 대해 비어 있는 아이는 0을 되돌려주지만 이 노드는 잎 노드가 아니기 때문에 되돌아오는 결과는 잘못된 것이다.
따라서 현재 처리된 노드에 한 아이가 비어 있는 것을 발견하면 최대치 INT_MAX, 결과를 방해하지 않습니다.

 1 class Solution {
 2 public:
 3     int minDepth(TreeNode *root) {
 4         if(!root) return 0;
 5         if(!root -> left && !root -> right) return 1;   //Leaf means should return depth.
 6         int leftDepth = 1 + minDepth(root -> left);
 7         leftDepth = (leftDepth == 1 ? INT_MAX : leftDepth);
 8         int rightDepth = 1 + minDepth(root -> right);
 9         rightDepth = (rightDepth == 1 ? INT_MAX : rightDepth);  //If only one child returns 1, means this is not leaf, it does not return depth.
10         return min(leftDepth, rightDepth);
11     }
12 };

 
물론 이 문제도 여러 차례 순서로 풀 수 있다.

class Solution {
struct LevNode{
    TreeNode* Node;
    int Lev;
};
public:
    int minDepth(TreeNode *root) {
        if(NULL == root) return 0;
        queue<LevNode> q;
        LevNode lnode;
        lnode.Node = root;
        lnode.Lev = 1;
        q.push(lnode);
        while(!q.empty()){
            LevNode curNode = q.front();
            q.pop();
            if(NULL == (curNode.Node) -> left && NULL == (curNode.Node) -> right)
                return (curNode.Lev);
            if(NULL != (curNode.Node) -> left){
                LevNode newNode;
                newNode.Node = (curNode.Node) -> left;
                newNode.Lev = (curNode.Lev + 1);
                q.push(newNode);
            }
            if(NULL != (curNode.Node) -> right){
                LevNode newNode;
                newNode.Node = (curNode.Node) -> right;
                newNode.Lev = (curNode.Lev + 1);
                q.push(newNode);
            }
        }
        return 0;
    }
};

 
이 문제에 대해 LeetCode 두 가지 해법의 시간은 모두 48ms이다
 

2. 두 갈래 나무의 최대 깊이

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
최대 깊이도 잎 노드까지의 길이지만 최대 깊이를 구하기 때문에 한 아이가 비어 있는 비잎 노드는 결과를 방해하지 않기 때문에 가장 간결한 처리 방식으로 해결할 수 있다.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode *root) {
        if(!root) return 0;
        int leftDepth = maxDepth(root -> left) + 1;
        int rightDepth = maxDepth(root -> right) + 1;
        return max(leftDepth, rightDepth);
    }
};