二叉树遍历(先序、中序、后序)

二叉树的节点类型

class TreeNode {
    int val;
    //左子树
    TreeNode left;
    //右子树
    TreeNode right;
    //构造方法
    TreeNode(int x) {
        val = x;
    }
}

先序遍历

// 递归先序遍历
public static void fun(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + "");
        fun(root.left);
        fun(root.right);
    }
}

// 非递归，需要使用到栈
public static void fun_2(TreeNode root) {
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode node = root;
    while(node != null || !stack.isEmpty()) {
        while(node != null) {
            System.out.print(node.val + "");
            stack.push(node);
            node = node.left;
        }
        if (!stack.isEmpty()) {
            node = stack.pop();
            node = node.right;
        }
    }
}