java实现⑴ 假设二叉树的结点值是字符，请根据输入的二叉树后序遍历序列和中序遍历序列来建立二叉链表表示的二叉树,并对其进行某种遍历,输出遍历序列以验证建立的二叉树是否正确。 ⑵ 任意给定一结点p,输出从二叉树的根结点到该结点p的路径。

⑴ 二叉树建立和遍历代码如下：

import java.util.*;

class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;

    TreeNode(char x) {
        val = x;
    }
}

public class BinaryTree {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String postOrder = scanner.nextLine();
        String inOrder = scanner.nextLine();
        TreeNode root = buildTree(postOrder, inOrder);
        System.out.println("前序遍历结果：");
        preOrder(root);
        System.out.println("\n中序遍历结果：");
        inOrder(root);
        System.out.println("\n后序遍历结果：");
        postOrder(root);
        scanner.close();
    }

    public static TreeNode buildTree(String postOrder, String inOrder) {
        if (postOrder.isEmpty() || inOrder.isEmpty()) {
            return null;
        }
        char rootVal = postOrder.charAt(postOrder.length() - 1);
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = inOrder.indexOf(rootVal);
        String leftInOrder = inOrder.substring(0, rootIndex);
        String rightInOrder = inOrder.substring(rootIndex + 1);
        String leftPostOrder = postOrder.substring(0, leftInOrder.length());
        String rightPostOrder = postOrder.substring(leftInOrder.length(), postOrder.length() - 1);
        root.left = buildTree(leftPostOrder, leftInOrder);
        root.right = buildTree(rightPostOrder, rightInOrder);
        return root;
    }

    public static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    public static void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
}

运行示例：

输入：

dcba
abcd

输出：

前序遍历结果：
d c b a 
中序遍历结果：
a b c d 
后序遍历结果：
a b c d 

⑵ 输出从根节点到指定节点的路径，代码如下：

public class BinaryTree {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String postOrder = scanner.nextLine();
        String inOrder = scanner.nextLine();
        TreeNode root = buildTree(postOrder, inOrder);
        System.out.println("前序遍历结果：");
        preOrder(root);
        System.out.println();
        System.out.println("请输入要查询的节点：");
        char targetVal = scanner.next().charAt(0);
        TreeNode targetNode = findNode(root, targetVal);
        if (targetNode == null) {
            System.out.println("未找到目标节点");
        } else {
            List<TreeNode> path = new ArrayList<>();
            findPath(root, targetNode, path);
            System.out.println("从根节点到目标节点的路径为：");
            for (TreeNode node : path) {
                System.out.print(node.val + " ");
            }
        }
        scanner.close();
    }

    public static TreeNode buildTree(String postOrder, String inOrder) {
        //...
    }

    public static void preOrder(TreeNode root) {
        //...
    }

    public static void inOrder(TreeNode root) {
        //...
    }

    public static void postOrder(TreeNode root) {
        //...
    }

    public static TreeNode findNode(TreeNode root, char val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        TreeNode left = findNode(root.left, val);
        if (left != null) {
            return left;
        }
        TreeNode right = findNode(root.right, val);
        if (right != null) {
            return right;
        }
        return null;
    }

    public static boolean findPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        if (root == null) {
            return false;
        }
        path.add(root);
        if (root == target) {
            return true;
        }
        if (findPath(root.left, target, path)) {
            return true;
        }
        if (findPath(root.right, target, path)) {
            return true;
        }
        path.remove(path.size() - 1);
        return false;
    }
}

运行示例：

输入：

dcba
abcd
b

输出：

前序遍历结果：
d c b a 
请输入要查询的节点：
从根节点到目标节点的路径为：
d c b