Java 求解二叉树的深度

末蓝、 2023-01-19 09:50 91阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、代码
     *  三、总结

## 一、题目 ##

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

--------------------

题解：  
该题有两种解法，可以采用 BFS（广度优先搜索），或者采用 DFS（深度优先搜索）

## 二、代码 ##

BFS:

import java.util.*;
    public class Solution { 
        public int TreeDepth(TreeNode root) { 
            if(root==null){ 
                return 0;
            }
            //设置队列
            Deque<TreeNode> deque = new LinkedList<>();
            deque.add(root);
            //表示树的长度
            int len = 0;
            while(!deque.isEmpty()){ 
                //此时队列的长度，也就是一层的队列节点个数
                int length = deque.size();
                for(int i=0;i<length;i++){ 
                    //队列是先进先出
                    TreeNode temp = deque.poll();
                    //左子树不空，左子树入队；右子树不空，右子树入队
                    if(temp.left !=null){ 
                        deque.add(temp.left);
                    }
                    if(temp.right !=null){ 
                        deque.add(temp.right);
                    }
                }
                len++;
            }
            return len;
        }
    }

DFS:

import java.util.*;
    public class Solution { 
        public int TreeDepth(TreeNode root) { 
            if(root==null){ 
                return 0;
            }
            int llen = TreeDepth(root.left);
            int rlen = TreeDepth(root.right);
            return Math.max(llen,rlen) + 1;
        }
    }

## 三、总结 ##

BFS：中心思想就是层序遍历，一层一层遍历,借助队列实现

DFS：中心思想是递归遍历，先左子树走到头，然后在右子树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]

> BFS：1,2,3,4,5,7  
> DFS：1,2,4,5,3,7

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]: /images/20221021/ec085336c92445ff9444b19f91d8dace.png