LeetCode 144: Binary Tree Preorder Traversal (Iterative Stack, Root-Left-Right)
LeetCode 144TreeDFSStackToday we solve LeetCode 144 - Binary Tree Preorder Traversal.
Source: https://leetcode.com/problems/binary-tree-preorder-traversal/
English
Problem Summary
Given the root of a binary tree, return its preorder traversal as a list of node values. Preorder order is Root - Left - Right.
Key Insight
Recursive DFS directly matches preorder definition, but iterative stack is often preferred in interviews because it shows explicit control of traversal state.
Brute Force and Limitations
The straightforward recursive solution is short and correct, but deep trees can cause call-stack overflow in strict environments. Iterative stack avoids that risk while keeping the same traversal order.
Optimal Algorithm Steps (Iterative Stack)
1) If root is null, return empty list.
2) Push root onto a stack.
3) While stack is not empty: pop node, append value to answer.
4) Push right child first, then left child.
5) Because stack is LIFO, left child is processed before right child, preserving preorder.
Complexity Analysis
Time: O(n), each node is visited once.
Space: O(h) average (tree height), O(n) worst-case for skewed tree.
Common Pitfalls
- Pushing left child before right child in iterative version (this breaks preorder).
- Forgetting null checks for children.
- Mixing preorder with inorder/postorder output order.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) return ans;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
ans.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return ans;
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}
ans := make([]int, 0)
stack := []*TreeNode{root}
for len(stack) > 0 {
n := len(stack)
node := stack[n-1]
stack = stack[:n-1]
ans = append(ans, node.Val)
if node.Right != nil {
stack = append(stack, node.Right)
}
if node.Left != nil {
stack = append(stack, node.Left)
}
}
return ans
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if (!root) return ans;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
ans.push_back(node->val);
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
return ans;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if root is None:
return []
ans = []
stack = [root]
while stack:
node = stack.pop()
ans.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return ans/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
if (root === null) return [];
const ans = [];
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
ans.push(node.val);
if (node.right !== null) stack.push(node.right);
if (node.left !== null) stack.push(node.left);
}
return ans;
};中文
题目概述
给定二叉树根节点 root，返回它的前序遍历结果。前序遍历顺序是 根 - 左 - 右。
核心思路
递归 DFS 最贴合定义；面试里常见的是迭代栈写法，因为它能体现你对遍历状态的显式控制。
暴力/直观解法与不足
最直观是递归，代码很短也正确；但在极深树上可能有调用栈深度风险。迭代栈可以避免这个问题，同时保持相同的访问顺序。
最优算法步骤（迭代栈）
1）若 root 为空，返回空数组。
2）把 root 入栈。
3）循环直到栈空：弹出节点，记录节点值。
4）先压右子节点，再压左子节点。
5）由于栈是后进先出，左子节点会先处理，从而得到前序顺序。
复杂度分析
时间复杂度：O(n)，每个节点访问一次。
空间复杂度：平均 O(h)（树高），最坏退化为 O(n)。
常见陷阱
- 迭代写法中把左右入栈顺序写反（会破坏前序）。
- 忘记判空导致空指针问题。
- 把前序和中序/后序的访问时机混淆。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) return ans;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
ans.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return ans;
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}
ans := make([]int, 0)
stack := []*TreeNode{root}
for len(stack) > 0 {
n := len(stack)
node := stack[n-1]
stack = stack[:n-1]
ans = append(ans, node.Val)
if node.Right != nil {
stack = append(stack, node.Right)
}
if node.Left != nil {
stack = append(stack, node.Left)
}
}
return ans
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if (!root) return ans;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
ans.push_back(node->val);
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
return ans;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if root is None:
return []
ans = []
stack = [root]
while stack:
node = stack.pop()
ans.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return ans/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
if (root === null) return [];
const ans = [];
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
ans.push(node.val);
if (node.right !== null) stack.push(node.right);
if (node.left !== null) stack.push(node.left);
}
return ans;
};
Comments