java 获取叶子节点_java遍历树,并得到每条根到叶子节点实现上移下移功能
时间: 2024-02-05 09:13:57 浏览: 30
可以使用递归的方式遍历树,并获取每一个叶子节点。具体实现如下:
```java
public class TreeNode {
private int val;
private TreeNode left;
private TreeNode right;
public TreeNode(int val) {
this.val = val;
}
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
public boolean isLeaf() {
return left == null && right == null;
}
}
public class TreeTraversal {
public static void main(String[] args) {
// 构造一棵二叉树
TreeNode root = new TreeNode(1);
root.setLeft(new TreeNode(2));
root.getLeft().setLeft(new TreeNode(4));
root.getLeft().setRight(new TreeNode(5));
root.setRight(new TreeNode(3));
root.getRight().setLeft(new TreeNode(6));
root.getRight().setRight(new TreeNode(7));
// 遍历树并获取每个叶子节点
List<TreeNode> leaves = new ArrayList<>();
traverse(root, new ArrayList<>(), leaves);
// 输出叶子节点的值
for (TreeNode leaf : leaves) {
System.out.println(leaf.getVal());
}
}
private static void traverse(TreeNode node, List<TreeNode> path, List<TreeNode> leaves) {
path.add(node);
if (node.isLeaf()) {
leaves.add(node);
return;
}
if (node.getLeft() != null) {
traverse(node.getLeft(), path, leaves);
path.remove(path.size() - 1);
}
if (node.getRight() != null) {
traverse(node.getRight(), path, leaves);
path.remove(path.size() - 1);
}
}
}
```
关于上移和下移功能,可以在遍历过程中记录每个叶子节点的路径,然后根据需要调整路径即可。比如,要把某个叶子节点上移一层,可以把该节点的路径的最后一个节点(也就是该节点本身)的父节点替换为父节点的父节点。要下移一层,则可以把该节点的路径的最后一个节点替换为其左右子节点中的任意一个。