一、题目描述

JZ38二叉树的深度
题目大意：给定一棵二叉树,求该数的高度

二、算法1（自底向上递归）

算法思路

1.总体思路：根据题意,树的深度是从根节点到叶子结点的所有路径中最长路径的长度,要到达叶子结点,要么走左子树要么走右子树,因此对于以某个结点为根节点构成的子树来说,它所表示的二叉树的深度就是以它右儿子为根的子树的深度+1和以它左儿子为根的子树的深度+1中的最大值
2.实现细节：对于空结点,它的深度为0,自底向上递归,即先递归到最底部,再逐步返回最优值至上层结点,还有一种写法是自顶向下递归,读者可以尝试写一下

代码实现（C++11）

class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
        return dfs(pRoot);
    }

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

时间复杂度：O(n)
空间复杂度：O(n)

三、算法2（BFS层序遍历）

算法思路

1.总体思路：层序遍历的遍历顺序是对数的结点一层一层遍历的,因此遍历的层数其实就是数的深度了
2.实现方法：用一个变量记录当前的深度,每次队列中存放的都是某一层的所有结点,每个结点出队时都尝试加入新的子节点进来

代码实现（C++11）

class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
        if(!pRoot) return 0;
        return bfs(pRoot);
    }

    int bfs(TreeNode* root){
        queue<TreeNode*> q;
        q.push(root);
        int depth = 0;
        while(q.size()){
            int s = q.size();    // 当前层数的结点数
            ++depth;
            for(int i = 0; i < s; i++){
                TreeNode* fa = q.front();
                q.pop();
                if(fa->left) q.push(fa->left);
                if(fa->right) q.push(fa->right);
                }
        }
        return depth;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)