剑指 offer：38、二叉树的深度

38. 二叉树的深度

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

解题思路：

• 思路1: 使用递归思路，属于DFS（深度优先搜索），时间复杂度为O(N)，空间复杂度：在最糟糕的情况下，树是完全不平衡的，例如每个结点只剩下左子结点，递归将会被调用N次（树的高度），因此保持调用栈的存储将是O(N)。但在最好的情况下（树是完全平衡的），树的高度将是log(N)。因此，在这种情况下的空间复杂度将是O(log(N))。
• 思路2: 使用迭代思路，引入一个栈，使用 DFS 策略访问每个结点，同时在每次访问时更新最大深度。时间复杂度为O(N)，空间复杂度将是O(N)。

解答：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
// 解法1:
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(!pRoot)
            return 0;
        return max(TreeDepth(pRoot->left) + 1, TreeDepth(pRoot->right) + 1);
    }
};
// 解法2:
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(!pRoot)
            return 0;
        queue<TreeNode *> que;
        que.push(pRoot);
        int depth = 0;
        while(!que.empty())
        {
            // 队列中每次迭代都只存储了一层的元素
            int size = que.size();
            depth++;
            for(int i = 0; i < size; ++i)
            {
                TreeNode *node = que.front();
                que.pop();
                if(node->left)
                    que.push(node->left);
                if(node->right)
                    que.push(node->right);
            }
        }
        return depth;
    }
};

大家有兴趣可以访问我的个人博客，不定时更新一些内容哦！

图片来自必应壁纸