144.二叉树的前序遍历

题目:144.二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

• 示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

• 示例 2：

输入：root = []
输出：[]

• 示例 3：

输入：root = [1]
输出：[1]

• 提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

• 进阶：

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路1

递归方法: 我们定义一个辅助函数 preorderHelper，它接收一个节点作为参数，递归地处理根节点、左子树和右子树。

• 时间复杂度:O(n)，其中 n 是二叉树的节点数
• 空间复杂度:O(h)，其中 h 是二叉树的高度

代码

// 递归前序遍历方法
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    if (root == null) {
        return result;
    }
    preorderHelper(result, root);
    return result;
}

// 递归辅助方法
private void preorderHelper(List<Integer> result, TreeNode node) {
    if (node == null) {
        return;
    }
    // 访问根节点
    result.add(node.val);
    // 访问左子树
    preorderHelper(result, node.left);
    // 访问右子树
    preorderHelper(result, node.right);
}

思路2

迭代方法: 使用栈来模拟递归的过程。

1. 使用栈来保存节点，从根节点开始，将其压入栈中。
2. 进入循环，每次从栈中弹出一个节点，访问该节点并将其值添加到结果列表中。
3. 先将右子节点压入栈，再将左子节点压入栈，这样在下次循环时，左子节点先被处理（符合前序遍历的顺序）。

• 时间复杂度:O(n)
• 空间复杂度:O(n)

代码

// 迭代前序遍历方法
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        // 先压入右子节点，再压入左子节点
        // 这样在下次循环时，左子节点先被处理
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    return result;
}