【剑指Offer】面试题55

题目

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

例如：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / 
  9  20
    /  
   15   7

返回它的最大深度 3 。

提示：
节点总数 <= 10000

本题同【LeetCode】104. 二叉树的最大深度

思路一：递归

代码

时间复杂度：O(n)，每个节点访问一次
空间复杂度：O(n)，树的高度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int res = 0;
        if (root) {
            if (!root->left && !root->right) return 1;
            res = max(maxDepth(root->left), maxDepth(root->right)) + 1;
        }
        return res;
    }
};

继续简化

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return 1 +  max(maxDepth(root->left), maxDepth(root->right));
    }
};

思路二：非递归层次遍历

代码

时间复杂度：O(n)，每个节点访问一次
空间复杂度：O(n)，树的最大宽度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int res = 0;        
        if (root) {
            queue<TreeNode*> que;
            que.push(root);
            while (!que.empty()) {
                for (int i = que.size(); i > 0; --i) {
                    TreeNode *node = que.front();
                    que.pop();
                    if (node->left) que.push(node->left);
                    if (node->right) que.push(node->right);                    
                }
                ++res;
            }
        }
        return res;
    }
};