思路

题目分析

1. 题目给出一棵二叉树，函数的参数一项为根节点指针
2. 我们需要返回这棵二叉树的高度

• 方法一：递归
  • 我们将目标函数理解为以root指针为树的根节点，返回该树的高度
  • 因此我们的目的就是递归地获得左子树高度，递归地获得右子树高度，在这两个高度数值中取出较大的数值，加上本身当前根节点的高度1，就是最终的结果
• 方法二：非递归层序
  • 我们用队列的方式来逐层存储结点
  • 队列中包含的信息是深度为同一深度的树的所有节点
  • 对当前层的结点执行压入左右子节点的操作，完成之后当前层结点自己要退出队列
  • 逐层的过程中统计树高度
  • 最终返回树高

方法一：递归

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    
    int maxDepth(TreeNode* root) {
        // write code here
        if(root == NULL) return 0;        // 判断当前是否为空节点，为空则返回高度0
        int l = maxDepth(root->left);     // 递归获取左子树的高度
        int r = maxDepth(root->right);    // 递归获得右子树的高度
        return 1 + max(l,r);              // 返回自身节点所占的1个高度加上左右子树最高的高度
    }
};

复杂度分析

• 时间复杂度：$O\left(N\right)O(N)$O(N)，每个节点都需要访问一次
• 空间复杂度：$O\left(N\right)O(N)$O(N)，递归函数栈的空间

方法二：非递归层序遍历

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxDepth(TreeNode* root) {
        // write code here
        if(root == NULL) return 0;                    // 判断是否为空
        queue<TreeNode*> q;                           // 用队列来层序存储结点
        int level = 0;                                // 最终返回的高度or层数
        q.push(root);                                 // 根节点入队
        while(!q.empty()){                            // 在队列不空的情况下
            level++;                                  // 树高++
            int n = q.size();                         // 获取当前队列大小
            while(n) {                                // 将当前队列中树的这一层的结点出队，并压入队左右子节点
                TreeNode* temp = q.front();           // 取队首
                q.pop();                              // 队首出队
                if(temp->left) q.push(temp->left);    // 左子节点入队
                if(temp->right) q.push(temp->right);  // 右子节点入队
                n--;                                  // 该层的结点数量--
            }
        }
        return level;                                 // 返回最终结果
    }
};

复杂度分析

• 时间复杂度：$O\left(N\right)O(N)$O(N)，所有节点需要访问一次
• 空间复杂度：$O\left(logN\right)O(logN)$O(logN)，队列最大一次空间占用即树的同一深度的一行结点数量，最大也是$O\left(logN\right)O(logN)$O(logN)级别