[牛客習題]二叉樹的深度

題目描述

輸入一棵二叉樹，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。

題目分析：

• 可以采用遞歸求解，也可以采用層次周遊
• 層次周遊的話我們需要借助隊列幫助我們周遊，先将根節點入隊，如果隊列不空則一直循環。循環内先拿到對頭節點再進行出隊，如果左右樹不空就入隊，根據隊列元素大小來确定執行次數，嗎，每完成一次層次周遊就将depth+1；
• 就如上圖所示，先将節點2入隊，經曆層次周遊後，5和4入隊，2出隊，進行第二層的周遊；5和4的左右樹都不空，再将它們的左右樹入隊，進行第三層的周遊...最終隊列為空得到樹的深度。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
        if(pRoot == nullptr)
            return 0;

        queue<TreeNode*> q;
        q.push(pRoot);
        int depth = 0;

        while(!q.empty())
        {
            int sz = q.size();
            depth++;

            for(int i = 0; i < sz; ++i)
            {
                TreeNode* node = q.front();
                q.pop();
                if(node->left)
                    q.push(node->left);

                if(node->right)
                    q.push(node->right);
            }
        }

        return depth;
    }
};           

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:   
    int TreeDepth(TreeNode* pRoot) {
        if(pRoot == nullptr)
            return 0;

        //最大的子樹深度就是整個樹的深度
        return 1 + max(TreeDepth(pRoot->left), TreeDepth(pRoot->right));
    }
}；