Leetcode
Tree
Depth-first Search
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. Remove the leaves [4, 5, 3] from the tree 1 / 2 2. Remove the leaf [2] from the tree 1 3. Remove the leaf [1] from the tree [] Returns [4, 5, 3], [2], [1].
分析¶
寻找二叉树的叶子节点。可以从例子中观察得到,节点在结果中的位置下标,等于以该节点为根节点的二叉树的深度。所以一个最直接的思路是该节点为根节点的二叉树的深度,在相应位置添加节点的值。
public List<List<Integer>> findLeaves(TreeNode root) { int height = maxHeight(root); List<List<Integer>> list = new ArrayList<>(); if (height == 0) return list; for (int i = 0; i < height; i++) list.add(new ArrayList<Integer>()); list.get(height - 1).add(root.val); traversal(list, root.left); traversal(list, root.right); return list; } private int maxHeight(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxHeight(root.left), maxHeight(root.right)); } private void traversal(List<List<Integer>> list, TreeNode root) { if (root == null) return; list.get(maxHeight(root) - 1).add(root.val); traversal(list, root.left); traversal(list, root.right); }
近期评论