TreeNode List 遍历

树的遍历有三种方式：前序遍历、中序遍历和后序遍历。对于每种遍历方式，我们都可以使用递归或非递归的方式来实现。下面是使用递归实现的代码：

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

// 前序遍历：根节点 -> 左子树 -> 右子树
void preorderTraversal(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorderTraversal(root.left);
    preorderTraversal(root.right);
}

// 中序遍历：左子树 -> 根节点 -> 右子树
void inorderTraversal(TreeNode root) {
    if (root == null) return;
    inorderTraversal(root.left);
    System.out.print(root.val + " ");
    inorderTraversal(root.right);
}

// 后序遍历：左子树 -> 右子树 -> 根节点
void postorderTraversal(TreeNode root) {
    if (root == null) return;
    postorderTraversal(root.left);
    postorderTraversal(root.right);
    System.out.print(root.val + " ");
}

对于非递归实现，我们可以使用栈来辅助实现。以前序遍历为例：

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

中序遍历和后序遍历的非递归实现可以参考以下代码：

// 中序遍历非递归实现
void inorderTraversal(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    while (!stack.isEmpty() || node != null) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        } else {
            node = stack.pop();
            System.out.print(node.val + " ");
            node = node.right;
        }
    }
}

// 后序遍历非递归实现
void postorderTraversal(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(root);
    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);
        if (node.left != null) {
            stack1.push(node.left);
        }
        if (node.right != null) {
            stack1.push(node.right);
        }
    }
    while (!stack2.isEmpty()) {
        System.out.print(stack2.pop().val + " ");
    }
}