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