二叉树前序遍历

递归

    public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList();
    traversal(root, list);
    return list;
}

private void traversal(TreeNode node, List<Integer> list) {
    if(node == null) {
        return;
    }
    list.add(node.val);
    traversal(node.left, list);
    traversal(node.right, list);
}

迭代法

    public List<Integer> preorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack();
    List<Integer> list = new ArrayList();
    if(root == null) {
        return list;
    }   
    stack.push(root);
    while(!stack.isEmpty()) {
        TreeNode node = stack.pop();
        list.add(node.val);
        if(node.right != null) {
            stack.push(node.right);
        }
        if(node.left != null) {
            stack.push(node.left);
        }
    }
    return list;
}

二叉树中序遍历

递归

    public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList();
    traversal(root, list);
    return list;
}
private void traversal(TreeNode node, List<Integer> list) {
    if(node == null) {
        return;
    }
    
    traversal(node.left, list);
            list.add(node.val);

    traversal(node.right, list);
}

迭代法

    public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList();
    Stack<TreeNode> stack = new Stack();
    TreeNode cur = root;
    while(!stack.isEmpty() || cur != null) {
        if(cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            TreeNode node = stack.pop();
            list.add(node.val);
            cur = node.right;
        }
    }
    return list;
}

二叉树后序遍历

递归

    public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList();
    traversal(root, list);
    return list;
}
private void traversal(TreeNode node, List<Integer> list) {
    if(node == null) {
        return;
    }
    
    traversal(node.left, list);
    traversal(node.right, list);
    list.add(node.val);
}

迭代法

    public List<Integer> postorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack();
    List<Integer> list = new ArrayList();
    if(root == null) {
        return list;
    }   
    stack.push(root);
    while(!stack.isEmpty()) {
        TreeNode node = stack.pop();
        list.add(node.val);
        if(node.left != null) {
            stack.push(node.left);
        }
        if(node.right != null) {
            stack.push(node.right);
        }
    }
    Collections.reverse(list);
    return list;
}