leetcode Minimum Depth of Binary Tree C++問題解

タイトルの説明
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.
最短パスを求めるツリーを与えます
最短パス定義:ルートノードから最も近いリーフノードへのパス上のノード数
構想の説明
この問題は私にとって考えが多い.
まず、比較的大きいが重要な概念を明確にし、二叉木は再帰的なデータ構造であるため、再帰的な思考能力を考察するための絶好のデータ構造である.再帰は深さ優先検索に違いない
まず、ツリーの高さを求めるコードを思い出します.

int treeHeight(TreeNode *root)
{
    if (root==NULL)
        return 0;
    int left=treeHeight(root->left);
    int right=treeHeight(root->right);
    return 1+max(left,right);
}

クラスはこのコードに比べて、私は上記のコードの1行だけを変更して提出しました.
return 1+min(left,right);
そこでWAについて、このようにした結果、葉ノードに対してその深さを計算したかどうかを考慮しないため、この問題は葉ノードでしか深さを判断できないことを要求し、葉ノードであるかどうかをどのように判断するかについては、ノードが空である場合には、兄弟ノードがあるかどうかを判断し、なければ、その空ノードの親ノードが葉ノードである場合、このノードの深さを0とし、その親ノードの深さを自然に1とし、兄弟ノード、すなわち空のノードの親ノードがリーフノードでない場合、そのノードの深さを正無限(INT_MAX)とする.非リーフノードの深さの比較は避けられる.具体的なコードは以下のように実現される.

class Solution {
public:
    int minDepth(TreeNode *root) 
    {
        return minDepth(root,false);
    }
private:
    int minDepth(TreeNode *root,bool hasBrother)
    {
        if(root==NULL)
        {
            return hasBrother?INT_MAX:0;

        }
        return 1+min(minDepth(root->left,root->right!=NULL),minDepth(root->right,root->left!=NULL));

    }
};

さらに、ツリーの再帰に対する認識について説明します.ツリーの再帰は、コードの順序が再帰可能な場所に実行され、最も奥に再帰され、階層的に上位に値を返した後、順序的に実行されます.
次に非再帰的な解法で,この木を遍歴し,各葉ノードの深さを統計し,最小値を更新し,遍歴中に現在の深さから遍歴を継続する必要があるか否かを判断し,枝切りを行うことに注意する.コードは次のように実装されます.

class Solution {
public:
    int minDepth(TreeNode *root) 
    {
        if (root==NULL)
            return 0;
        int result=INT_MAX;
        stack<pair<TreeNode *,int> > s;  //             
        s.push(make_pair(root,1));//     
        while(!s.empty()) //       ，           ，                 
        {
            auto node=s.top().first;
            auto depth=s.top().second;
            s.pop();
            if(node->left==NULL && node->right==NULL)   //        
                result=min(result,depth);
            if(node->left && depth<result) //    ，  ，          
                s.push(make_pair(node->left,depth+1));
            if(node->right && depth<result)
                s.push(make_pair(node->right,depth+1));


        }
        return result;
    }

};