如何使用递归返回从树根到目标的树节点的ArrayList？

使用递归返回从树根到目标的树节点的ArrayList的方法如下：

首先，我们需要定义一个树节点的数据结构，包含节点值和指向子节点的指针。
创建一个空的ArrayList来存储结果。
编写递归函数，该函数接受当前节点和目标节点作为参数。
在递归函数中，首先检查当前节点是否为空。如果为空，则返回空的ArrayList。
然后，检查当前节点是否为目标节点。如果是，则创建一个只包含当前节点值的ArrayList，并返回。
如果当前节点不是目标节点，则递归调用函数来搜索当前节点的子节点。
将子节点返回的ArrayList添加到当前节点的值之前，并返回新的ArrayList。
在主函数中，调用递归函数，并将树的根节点和目标节点作为参数传递。

下面是一个示例代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class TreeTraversal {
    public static ArrayList<Integer> findPath(TreeNode root, TreeNode target) {
        ArrayList<Integer> path = new ArrayList<>();
        if (root == null) {
            return path;
        }
        
        if (root == target) {
            path.add(root.val);
            return path;
        }
        
        ArrayList<Integer> leftPath = findPath(root.left, target);
        if (!leftPath.isEmpty()) {
            path.addAll(leftPath);
            path.add(root.val);
            return path;
        }
        
        ArrayList<Integer> rightPath = findPath(root.right, target);
        if (!rightPath.isEmpty()) {
            path.addAll(rightPath);
            path.add(root.val);
            return path;
        }
        
        return path;
    }
    
    public static void main(String[] args) {
        // 创建一个示例树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        
        // 查找从根节点到目标节点5的路径
        TreeNode target = root.left.right;
        ArrayList<Integer> path = findPath(root, target);
        
        // 输出路径
        for (int i = path.size() - 1; i >= 0; i--) {
            System.out.print(path.get(i) + " ");
        }
    }
}

这个例子中，我们创建了一个包含7个节点的二叉树。然后，我们使用递归函数findPath来查找从根节点到目标节点5的路径。最后，我们按照从根节点到目标节点的顺序输出路径节点的值。输出结果为：1 2 5。

腾讯云相关产品和产品介绍链接地址：