用递归算法遍历树,将树的最后一级取出组成新数组
时间: 2023-06-19 20:04:59 浏览: 28
假设树的节点结构如下:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
```
可以使用递归算法遍历树,将树的最后一级取出组成新数组。代码如下:
```java
public int[] getLeaves(TreeNode root) {
List<Integer> leaves = new ArrayList<>();
getLeavesHelper(root, leaves);
int[] result = new int[leaves.size()];
for (int i = 0; i < leaves.size(); i++) {
result[i] = leaves.get(i);
}
return result;
}
private void getLeavesHelper(TreeNode root, List<Integer> leaves) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
leaves.add(root.val);
} else {
getLeavesHelper(root.left, leaves);
getLeavesHelper(root.right, leaves);
}
}
```
首先定义一个空的列表 `leaves`,用于存储最后一级节点的值。然后调用递归辅助函数 `getLeavesHelper`,遍历树的所有节点。如果当前节点是叶子节点,则将其值添加到 `leaves` 列表中;否则,递归遍历当前节点的左子树和右子树。最后,将 `leaves` 列表转换为数组并返回。