方法一：递归

➡️ 前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }
    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) { // 递归结束条件
            return;
        }
        res.add(root.val); // 根左右
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

• 时间复杂度：O(n)，其中n 是二叉树的节点数。每一个节点恰好被遍历一次。
• 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(log⁡n)，最坏情况下树呈现链状，为 O(n)。

➡️ 中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }
    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

➡️ 后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }
    public void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
}

方法二：迭代

➡️ 前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        while(root != null || !stack.isEmpty()){
            while(root != null) {
                res.add(root.val); //根
                stack.push(root);
                root = root.left; // 左
            }
            root = stack.pop();
            root = root.right; // 右
        }
        return res;
    }
}

image.png

image.png

image.png

image.png

返回结果 res=[ 1,2,4,3,5,6]

➡️ 中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        while(root != null || !stack.isEmpty()){
            while(root != null) { 
                stack.push(root);
                root = root.left; // 左
            }
            root = stack.pop();
            res.add(root.val); //根
            root = root.right; // 右
        }
        return res;
    }
}

➡️ 后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null; // 主要用来记录右子节点，用于判断是否已遍历过
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left; // 左
            }
            root = stack.pop();
            if (root.right != null && root.right != prev) { // 右子树不为空，且没有遍历过
                // 再次入栈
                stack.push(root);
                root = root.right; // 右
            } else {
                res.add(root.val); // 根
                prev = root;
                root = null;
            }
        }
        return res;
    }
}

image.png

image.png

image.png