计算二叉树的深度

r囧r小猫 2022-12-29 00:23 144阅读 0赞

### 题目描述： ###

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

树的遍历方式总体分为两类：深度优先搜索(DFS)、广度优先搜索(BFS)；

*  常见的DFS：先序遍历、中序遍历、后序遍历
 *  常见的BFS：层序遍历（即按层遍历）

### 后序遍历： ###

树的深度就等于左子树的深度与右子树的深度中最大值加上1。

### 算法java实现： ###

public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }

### 复杂度分析： ###

*  时间复杂度：O(n)，n为树的节点数，计算树的深度要遍历所有节点
 *  空间复杂度：O(n)，最差情况下，递归深度为n

### 层序遍历： ###

*  树的层序遍历/广度优先搜索往往利用队列实现
 *  关键点：每遍历一层，则计数器加一，直到遍历完成，则可得到树的深度

### 算法解析： ###

*  特例处理：当root为空，直接返回深度0
 *  初始化：队列queue（加入根节点root），计数器res = 0
 *  循环遍历：当queue为空时跳出
 *  初始化一个空列表tmp，用于临时存储下一层节点
 *  遍历队列：遍历queue中的各个节点node，并将左子节点和右子节点加入tmp
 *  更新队列：执行queue = tmp，将下一层节点赋值给queue
 *  统计层数：执行res += 1,代表层数加1
 *  返回res即可

### java实现： ###

public int maxDepth(TreeNode root){
        if (root == null)
            return 0;
        List<TreeNode> queue = new LinkedList<>() {
       { add(root); }}, tmp;
        int res = 0;
        while(!queue.isEmpty()) {
            tmp = new LinkedList<>();
            for (TreeNode node : queue) {
                if(node.left != null)
                    tmp.add(node.left);
                if(node.right != null)
                    tmp.add(node.right);
            }
            queue = tmp;
            res++;
        }
    }

### 复杂度分析： ###

*  时间复杂度：O(n)，n为树的节点数量，计算树的深度需要遍历所有节点
 *  空间复杂度：O(n)，最差情况下，队列queue同时存储n/2个节点