【leetcode】366.Find Leaves of Binary Tree
2024-08-27 04:58:19
原题
Given a binary tree, collect a tree's nodes as if you were doing this:
Collect and remove all leaves, repeat until the tree is empty.
Example:
Given binary tree
1
/
2 3
/
4 5
Returns [4, 5, 3], [2], [1].
Explanation:
- Removing the leaves [4, 5, 3] would result in this tree:
1
/
2 - Now removing the leaf [2] would result in this tree:
1 - Now removing the leaf [1] would result in the empty tree:
[]
Returns [4, 5, 3], [2], [1].
解析
给一颗二叉树，
返回这个二叉树的叶子节点，每一次一组，依次放在List中
思路
我的思路：每一次深度遍历收割一次叶子放在结果中（缺点：深度有多少，就要深度遍历多少次）
优化算法：深度优选搜索，叶子节点深度标记为0，其他节点的深度标记为左右叶子节点较大的深度+1；相同深度的放在一个结果节点中
我的解法
public List<List<Integer>> FindLeaves(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
while (root != null) {
List<Integer> re = new ArrayList<>();
if (DFSTree(root, re)) {
root = null;
}
result.add(re);
}
return result;
}
private boolean DFSTree(TreeNode root, List<Integer> re) {
if (root.left == null && root.right == null) {
re.add(root.val);
return true;
}
if (root.left != null) {
if (DFSTree(root.left, re)) {
root.left = null;
}
}
if (root.right != null) {
if (DFSTree(root.right, re)) {
root.right = null;
}
}
return false;
}
最优解
public List<List<Integer>> FindLeavesOptimize(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
DFSTreeOptimize(root, result);
return result;
}
private int DFSTreeOptimize(TreeNode root, List<List<Integer>> result) {
if (root.left == null && root.right == null) {
if (result.size() <= 0) {
result.add(0, new ArrayList<>());
}
result.get(0).add(root.val);
return 0;
}
int deep, leftDeep = 0, rightDeep = 0;
if (root.left != null) {
leftDeep = DFSTreeOptimize(root.left, result);
}
if (root.right != null) {
rightDeep = DFSTreeOptimize(root.right, result);
}
deep = Math.max(leftDeep, rightDeep) + 1;
if (result.size() <= deep) {
result.add(deep, new ArrayList<>());
}
result.get(deep).add(root.val);
return deep;
}
最新文章
- C#-WebForm-简单控件
- 《JS高程》实现继承的6种方式（完整版）
- CMDB反思5
- 关于设置MX记录
- Joomla安装图文教程 （送 Joomla 中文语言包）
- 转：etc/fstab 文件详解
- （原）配置vs2013使用intel的IPP库
- Oracle 11g OCM 考试大纲
- PHPsthdy+xdebug
- ROS * 了解xacro的编写
- 01_新建WebApi后端服务项目
- 每天进步一点点——mysql——mysqlbinlog
- 9.7 dubbo心跳机制
- domino server端的Notes.ini详解
- Async、Await
- [C#]做服务使用Process启动外部程序没窗体
- MatCap冰冻效果Shader
- debian之apt源
- Tdrag
- storm-kafka