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