java遍历二叉树的三种方法实现

Java 遍历二叉树的三种方法是前序遍历、中序遍历和后序遍历，下面是它们的实现方式：

1. 前序遍历

前序遍历的顺序是先访问根节点，再遍历左子树，最后遍历右子树。实现方式如下：

public void preOrderTraversal(Node node) {
    if (node != null) {
        System.out.print(node.val + " ");
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

2. 中序遍历

中序遍历的顺序是先遍历左子树，再访问根节点，最后遍历右子树。实现方式如下：

public void inOrderTraversal(Node node) {
    if (node != null) {
        inOrderTraversal(node.left);
        System.out.print(node.val + " ");
        inOrderTraversal(node.right);
    }
}

3. 后序遍历

后序遍历的顺序是先遍历左子树，再遍历右子树，最后访问根节点。实现方式如下：

public void postOrderTraversal(Node node) {
    if (node != null) {
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        System.out.print(node.val + " ");
    }
}

以上三种遍历方式都可以采用递归实现，也可以采用迭代实现。递归实现比较简单，下面给出迭代实现的代码：

1. 前序遍历迭代实现

public void preOrderTraversal(Node root) {
    if (root == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        System.out.print(node.val + " ");
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

2. 中序遍历迭代实现

public void inOrderTraversal(Node root) {
    if (root == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    Node node = root;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        System.out.print(node.val + " ");
        node = node.right;
    }
}

3. 后序遍历迭代实现

public void postOrderTraversal(Node root) {
    if (root == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    Stack<Node> result = new Stack<>();
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        result.push(node);
        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.right != null) {
            stack.push(node.right);
        }
    }
    while (!result.isEmpty()) {
        System.out.print(result.pop().val + " ");
    }
}

以上是 Java 遍历二叉树的三种方法的实现，其中迭代实现比递归实现稍微复杂一些，但也更加灵活。