Java 求解二叉树的深度-蒲公英云

Java 求解二叉树的深度

末蓝、 2023-01-19 09:50 238阅读 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;
    }
}