剑指offer--55 - I. 二叉树的深度

深碍√TFBOYSˉ_ 2023-02-20 06:28 9阅读 0赞

## 题目描述 ##

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

**例如：**

给定二叉树 \[3,9,20,null,null,15,7\]，

3  
/  
9 20  
/  
15 7  
返回它的最大深度 3 。

**提示：**

节点总数 <= 10000

## 思路：递归，层次遍历（队列） ##

数的遍历可以分为：深度优先搜索DFS、广度优先搜索BFS  
`深度优先搜索`一般利用`递归、栈`实现  
`广度优先搜索`一般利用`队列`实现

## 解决方法 ##

一、递归  
**树的深度**：左子树的深度和右子树深度的最大值 +1  
**终止条件**：当root为null时，返回0

**时间复杂度**：O(n)，计算树的深度需要遍历所有节点  
**空间复杂度**：O(n)，最坏的情况（当树退化为链表时）

`递归解法`分别求出左子树、右子树的深度，比较左子树、右子树的深度，选出最大的一个，再加1就是二叉树的深度

/**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        
        public int TreeDepth(TreeNode root) {
        
            if(root == null){
        
                return 0;
            }
            int left = TreeDepth(root.left);
            int right = TreeDepth(root.right);
            return (left>right) ? (left+1) : (right+1);
        }
    }

二、层序遍历  
树的层序遍历 / 广度优先搜索往往利用 **`队列`** 实现。  
LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。  
**时间复杂度**：O(n) 访问树的每个节点  
**空间复杂度**：O(n) 最坏情况下（当树平衡时），队列同时存储n/2个节点

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public int maxDepth(TreeNode root) {
        
            if(root == null) return 0;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);  //根节点添加到queue队列中
            int depth=0;  //树的深度
            while(!queue.isEmpty()){
        
                int num = queue.size();
                for(int i=0; i<num; i++){
        
                    TreeNode node = queue.poll();  //返回队列的第一个节点并删除
                    if(node.left != null) queue.offer(node.left);  //左子树不为空时添加到队列中
                    if(node.right != null) queue.offer(node.right);
                }
                depth++;
            }
            return depth;
        }
    }