Java二叉树编写，代码不一样，结果却一样

Question

编写二叉树代码，中序遍历和后序遍历的结果一样，但先序遍历结果正常，这是为啥？

Answer 1

引自免费微信小程序：皆我百晓生

根据您提供的信息，看起来您正在尝试实现一个二叉树，并且遇到了中序遍历和后序遍历结果相同的问题。首先，让我们回顾一下二叉树的三种遍历方式：

1. 先序遍历 (Pre-order traversal): 根 -> 左 -> 右
2. 中序遍历 (In-order traversal): 左 -> 根 -> 右
3. 后序遍历 (Post-order traversal): 左 -> 右 -> 根

对于您提到的中序遍历和后序遍历结果相同的情况，这可能是因为二叉树具有某种特殊结构。在这种情况下，二叉树的左子树为空，或者右子树为空，或者整个树只包含一个节点。

为了更好地理解您的问题，您提供了四个部分的截图，但我注意到这些截图中的文字和代码并不完全相关联。不过，我可以根据您的描述提供一个简单的二叉树类（BinaryTree）以及相关的遍历方法。这个例子将展示如何构建一个二叉树并进行遍历。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTree {
    private TreeNode root;

    public BinaryTree(String preOrderTraversal) {
        this.root = buildTree(preOrderTraversal, 0, preOrderTraversal.length());
    }

    private TreeNode buildTree(String preOrderTraversal, int start, int end) {
        if (start >= end) {
            return null;
        }

        TreeNode node = new TreeNode(Integer.parseInt(preOrderTraversal.charAt(start++) + ""));
        if (start < end) {
            node.left = buildTree(preOrderTraversal, start, findRightmostNonEmptyNode(preOrderTraversal, start, end));
            node.right = buildTree(preOrderTraversal, findRightmostNonEmptyNode(preOrderTraversal, start, end) + 1, end);
        }
        return node;
    }

    // Find the index of the rightmost non-empty node in a substring
    private int findRightmostNonEmptyNode(String str, int start, int end) {
        for (int i = end - 1; i >= start; i--) {
            if (!Character.isDigit(str.charAt(i))) {
                return i;
            }
        }
        return start;
    }

    // In-order traversal
    public void inorderTraversal(TreeNode node) {
        inorderTraversalHelper(node);
    }

    private void inorderTraversalHelper(TreeNode node) {
        if (node != null) {
            inorderTraversalHelper(node.left);
            System.out.print(node.val + " ");
            inorderTraversalHelper(node.right);
        }
    }

    // Post-order traversal
    public void postorderTraversal(TreeNode node) {
        postorderTraversalHelper(node);
    }

    private void postorderTraversalHelper(TreeNode node) {
        if (node != null) {
            postorderTraversalHelper(node.left);
            postorderTraversalHelper(node.right);
            System.out.print(node.val + " ");
        }
    }

    public static void main(String[] args) {
        String preOrderTraversal = "AB.DF.G.C.E.H.";
        BinaryTree tree = new BinaryTree(preOrderTraversal);
        System.out.println("In-order traversal: ");
        tree.inorderTraversal(tree.root);
        System.out.println("\nPost-order traversal: ");
        tree.postorderTraversal(tree.root);
    }
}

这段代码定义了一个二叉树类，并实现了从扩展先序遍历序列构建二叉树的功能。然后，它包含了中序遍历（inorderTraversal）和后序遍历（postorderTraversal）方法。您可以将这段代码复制到您的项目中运行，看看是否解决了您的问题。

如果您想进一步调试您的代码，可以逐步分析 buildTree 方法，确保它正确地构建了二叉树结构。同时检查您的遍历函数，确认它们按照正确的顺序访问节点。