剑指offer 38. 二叉树的深度

38. 二叉树的深度

题目描述

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }

法一：递归遍历

 1 class Solution {
 2 public:
 3     // 前序递归遍历，分别统计左右子树的高度
 4     int preOrder(TreeNode* pRoot){
 5         if(pRoot){
 6             int leftH = preOrder(pRoot->left);
 7             int rightH = preOrder(pRoot->right);
 8             if(leftH >= rightH){
 9                 return leftH + 1;
10             }else{
11                 return rightH + 1;
12             }
13         }
14         return 0;
15     }
16     
17     int TreeDepth(TreeNode* pRoot)
18     {
19         return preOrder(pRoot);
20     }
21 };

Java实现：

 1 class Solution {
 2     // 递归方式
 3     public int maxDepth(TreeNode root) {
 4         // 如果root不为空，递归统计左右子树的高度
 5         if(root != null){
 6             int leftDepth = maxDepth(root.left);
 7             int rightDepth = maxDepth(root.right);
 8             // 返回左右子树高度的稍大者+1
 9             return (leftDepth >= rightDepth ? leftDepth : rightDepth) + 1;
10         }else{        // 如果root为空，直接返回0
11             return 0;
12         }
13     }
14 }

leetcode运行时间为0ms，空间为39.1mb

复杂度分析：

时间复杂度：对个每个结点都进行了一次遍历，所以复杂度复杂度为O(n)

空间复杂度：递归栈的深度为O(logn)

法二：层序遍历

利用队列实现层序遍历，用一个变量记录当前深度的结点个数，每出队一个结点，入队两个子节点后计数器加一，如果当前层的所有结点都已经出队完毕（计数器的值等于当前深度的结点个数），层数加一，计数器重置，当前层结点个数更新

 1 class Solution {
 2 public:
 3     
 4     int TreeDepth(TreeNode* pRoot)
 5     {
 6         // 层序遍历统计深度
 7         queue<TreeNode*> Q;
 8         if(pRoot != NULL){
 9             Q.push(pRoot);
10         }
11         int dep = 0, count = 0, nextCount = Q.size();    // nextCount 存储的是当前层数的结点个数
12         while(!Q.empty()){
13             TreeNode* node = Q.front();
14             Q.pop();
15             count++;
16             if(node->left)
17                 Q.push(node->left);
18             if(node->right)
19                 Q.push(node->right);
20             // 如果当前层的所有结点都已经出队完毕，层数加一，计数器重置，当前层结点个数更新
21             if(count == nextCount){
22                 dep++;
23                 count = 0;
24                 nextCount = Q.size();
25             }
26         }
27         return dep;
28     }
29 };

Java实现

抛出当前层左右结点，将下层结点入队，队列中的元素个数即为当前层的结点个数

 1 class Solution {
 2     // 层序遍历方式
 3     public int maxDepth(TreeNode root) {
 4         Queue<TreeNode> queue = new LinkedList<TreeNode>();
 5         if(root == null){
 6             return 0;
 7         }
 8         queue.offer(root);
 9         int layer = 0;
10         int count = 0;
11         while(!queue.isEmpty()){
12             // 抛出当前层左右结点，将下层结点入队
13             count = queue.size();　　// 队列中的元素个数即为当前层的结点个数
14             for(int i = 0; i < count; i++){
15                 TreeNode top = queue.poll();
16                 if(top.left != null){
17                     queue.offer(top.left);
18                 }
19                 if(top.right != null){
20                     queue.offer(top.right);
21                 }
22             }
23             layer++;
24         }
25         return layer;
26     }
27 }

leetcode运行时间为1ms，空间为38.6mb

复杂度分析：

时间复杂度：同样是把每个元素都入队出队了一次，所以时间复杂度为O(n)

空间复杂度：空间复杂度为树每层结点个数的最大值，即为O(n)