剑指Offer-38-求二叉树的深度--简单

    科技2025-07-08  7

    JZ38-求二叉树的深度-简单

    题目简介思路讲解算法实现实验结果涉及到的算法思想

    题目简介

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

    思路讲解

    二叉树的深度指的是从二叉树根节点到叶子节点左右路径中,最长路径的长度,比较容易想到的就是先求出所有到叶子节点的路径,最后求出最长路径的长度即可。 算法中使用两个全局变量,一个用来保存单条路径path,一个用来保存每条路径的长度pathsLen,使用java,util.Collections.max()可以找出最大值。

    算法实现

    import java.util.*; public class Solution { ArrayList<Integer> path = new ArrayList<Integer>(); //保存单条路径 ArrayList<Integer> pathsLen = new ArrayList<Integer>();//保存每条路径的长度 //辅助求二叉树深度 public void FindAllPath(TreeNode root){ if(root==null) { return; } path.add(root.val); // 把当前节点加入到路径当中 if(root.left==null&&root.right==null){ pathsLen.add(path.size()); //说明已经达到叶子节点,一条路径遍历结束 } if(root.left!=null){ FindAllPath(root.left); } if(root.right!=null){ FindAllPath(root.right); } path.remove(path.size()-1);//以当前节点为根节点的所有路径都已经遍历完全,回溯 } public int TreeDepth(TreeNode root) { if(root==null) return 0; FindAllPath(root); ArrayList<Integer> depth = pathsLen; return Collections.max(depth); } }

    实验结果

    涉及到的算法思想

    回溯法算法思想可参考: https://blog.csdn.net/pentiumCM/article/details/105306052

    Processed: 0.010, SQL: 8