Leetcode: Find Leaves of Binary Tree
LeetCode of Find Tree Binary
2023-09-11 14:14:07 时间
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: 1. Removing the leaves [4, 5, 3] would result in this tree: 1 / 2 2. Now removing the leaf [2] would result in this tree: 1 3. Now removing the leaf [1] would result in the empty tree: [] Returns [4, 5, 3], [2], [1].
Better Solution: https://discuss.leetcode.com/topic/49194/10-lines-simple-java-solution-using-recursion-with-explanation/2
For this question we need to take bottom-up approach. The key is to find the height of each node. The height of a node is the number of edges from the node to the deepest leaf.
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public List<List<Integer>> findLeaves(TreeNode root) { 12 List<List<Integer>> res = new ArrayList<>(); 13 helper(root, res); 14 return res; 15 } 16 17 public int helper(TreeNode cur, List<List<Integer>> res) { 18 if (cur == null) return -1; 19 int level = 1 + Math.max(helper(cur.left, res), helper(cur.right, res)); 20 if (res.size() <= level) 21 res.add(new ArrayList<Integer>()); 22 res.get(level).add(cur.val); 23 cur.left = cur.right = null; 24 return level; 25 } 26 }
First time solution: HashSet+ DFS
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public List<List<Integer>> findLeaves(TreeNode root) { 12 ArrayList<List<Integer>> res = new ArrayList<List<Integer>>(); 13 if (root == null) return res; 14 HashSet<TreeNode> visited = new HashSet<>(); 15 while (!visited.contains(root)) { 16 ArrayList<Integer> leaves = new ArrayList<Integer>(); 17 helper(root, leaves, visited); 18 res.add(new ArrayList<Integer>(leaves)); 19 } 20 return res; 21 } 22 23 public void helper(TreeNode cur, ArrayList<Integer> leaves, HashSet<TreeNode> visited) { 24 if ((cur.left==null || visited.contains(cur.left)) && (cur.right==null || visited.contains(cur.right))) { 25 leaves.add(cur.val); 26 visited.add(cur); 27 return; 28 } 29 if (cur.left!=null && !visited.contains(cur.left)) 30 helper(cur.left, leaves, visited); 31 if (cur.right!=null && !visited.contains(cur.right)) 32 helper(cur.right, leaves, visited); 33 } 34 }
相关文章
- [LeetCode] Number of 1 Bits & Reverse Integer - 整数问题系列
- [LeetCode] Length of Last Word - 最后一个单词的长度
- Leetcode 之Length of Last Word(37)
- leetcode 之Median of Two Sorted Arrays(五)
- Java实现 LeetCode 688 “马”在棋盘上的概率(DFS+记忆化搜索)
- Java实现 LeetCode 541 反转字符串 II(暴力大法)
- Java实现 LeetCode 504 七进制数
- Java实现 LeetCode 509 斐波那契数
- Java实现 LeetCode 496 下一个更大元素 I
- Java实现 LeetCode 413 等差数列划分
- Java实现 LeetCode 229 求众数 II(二)
- Java实现 LeetCode 88 合并两个有序数组
- 每日一道 LeetCode (12):最大子序和
- LeetCode:4_Median of Two Sorted Arrays | 求两个排序数组的中位数 | Hard
- LeetCode:104_Maximum Depth of Binary Tree | 二叉树的最大深度 | Easy
- [Javascript] Use an Array of Promises with a For Await Of Loop
- [LeetCode] Reverse Vowels of a String
- [LeetCode] Number of Islands
- [LeetCode] Bitwise AND of Numbers Range
- [LeetCode] Reverse Words in a String
- LeetCode(55): 跳跃游戏
- ( “树” 之 DFS) 617. 合并二叉树 ——【Leetcode每日一题】
- Python 刷Leetcode题库,顺带学英语单词(48)
- Leetcode学习计划之动态规划入门day6(152, 1567)
- 【LeetCode 90】子集 II
- LeetCode_Lowest Common Ancestor of a Binary Search Tree (Binary Tree)
- Leetcode 824. 山羊拉丁文(可以,一次过)
- Leetcode 796. 旋转字符串
- [LeetCode] 231. Power of Two ☆(是否2 的幂)
- [LeetCode] 191. Number of 1 Bits ☆(位 1 的个数)
- 【LeetCode】Reorder List 解题报告
- leetcode 326. Power of Three
- leetcode 371. Sum of Two Integers
- leetcode 104. Maximum Depth of Binary Tree
- leetcode 566. Reshape the Matrix
- 【LeetCode】152.乘积最大子数组