java编程求从二叉树根结点到到指定结点p之间的路径

可以使用递归的方式实现从二叉树根结点到指定结点p之间的路径。

首先，需要定义一个函数来搜索二叉树中的指定结点p：

public TreeNode searchNode(TreeNode root, TreeNode p) {
    if (root == null || p == null) {
        return null;
    }
    if (root == p) {
        return root;
    }
    TreeNode left = searchNode(root.left, p);
    if (left != null) {
        return left;
    }
    TreeNode right = searchNode(root.right, p);
    if (right != null) {
        return right;
    }
    return null;
}

接下来，定义一个函数来获取从根结点到指定结点p之间的路径：

public List<TreeNode> getPath(TreeNode root, TreeNode p) {
    List<TreeNode> path = new ArrayList<>();
    if (root == null || p == null) {
        return path;
    }
    TreeNode node = searchNode(root, p);
    if (node == null) {
        return path;
    }
    getPathHelper(root, node, path);
    return path;
}

在 getPathHelper 函数中，使用递归的方式获取路径，如果找到指定结点p，则返回 true，否则返回 false：

private boolean getPathHelper(TreeNode root, TreeNode p, List<TreeNode> path) {
    if (root == null) {
        return false;
    }
    if (root == p) {
        path.add(root);
        return true;
    }
    if (getPathHelper(root.left, p, path) || getPathHelper(root.right, p, path)) {
        path.add(root);
        return true;
    }
    return false;
}

完整代码如下：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BinaryTreePath {
    public TreeNode searchNode(TreeNode root, TreeNode p) {
        if (root == null || p == null) {
            return null;
        }
        if (root == p) {
            return root;
        }
        TreeNode left = searchNode(root.left, p);
        if (left != null) {
            return left;
        }
        TreeNode right = searchNode(root.right, p);
        if (right != null) {
            return right;
        }
        return null;
    }

    public List<TreeNode> getPath(TreeNode root, TreeNode p) {
        List<TreeNode> path = new ArrayList<>();
        if (root == null || p == null) {
            return path;
        }
        TreeNode node = searchNode(root, p);
        if (node == null) {
            return path;
        }
        getPathHelper(root, node, path);
        return path;
    }

    private boolean getPathHelper(TreeNode root, TreeNode p, List<TreeNode> path) {
        if (root == null) {
            return false;
        }
        if (root == p) {
            path.add(root);
            return true;
        }
        if (getPathHelper(root.left, p, path) || getPathHelper(root.right, p, path)) {
            path.add(root);
            return true;
        }
        return false;
    }
}