144. 二叉树的前序遍历

题目描述

输入二叉树的根节点 root，按前序遍历的次序返回所有节点值。

前序遍历：先访问当前节点，再前序遍历左子树，最后前序遍历右子树。

空树返回 []。树用层序数组表示，null 代表空位。

示例 1

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

解释：根 1 没有左孩子，右孩子是 2，3 是 2 的左孩子。

示例 2

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]

解释：先走完左子树 2,4,5,6,7，再走右子树 3,8,9。

示例 3

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

解释：空树。

示例 4

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

数据范围

节点总数在 [0, 100] 之间。
-100 <= Node.val <= 100

进阶：递归写法很直接，能否改用迭代实现？

解题思路：显式栈迭代

用一个显式栈代替递归。弹出栈顶节点就立刻记录它（根先访问），然后先压右孩子、再压左孩子。栈是后进先出的，所以左孩子会先被弹出，整棵左子树处理完后才轮到右孩子。

为什么正确

栈中存的是尚未访问的子树根；栈顶是前序中下一个要访问的节点。

复杂度分析

时间 O(n)，空间 O(h)。

易错点

压栈顺序是先右后左，弹出顺序才是先左后右。写反了会得到“根 → 右 → 左”。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = [root] if root else []
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res

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

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        vector<TreeNode*> stack;
        if (root) stack.push_back(root);
        while (!stack.empty()) {
            TreeNode* node = stack.back();
            stack.pop_back();
            res.push_back(node->val);
            if (node->right) {
                stack.push_back(node->right);
            }
            if (node->left) {
                stack.push_back(node->left);
            }
        }
        return res;
    }
};

func preorderTraversal(root *TreeNode) []int {
	res := []int{}
	stack := []*TreeNode{}
	if root != nil {
		stack = append(stack, root)
	}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, node.Val)
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}
	return res
}

var preorderTraversal = function(root) {
    const res = [];
    const stack = root ? [root] : [];
    while (stack.length) {
        const node = stack.pop();
        res.push(node.val);
        if (node.right) {
            stack.push(node.right);
        }
        if (node.left) {
            stack.push(node.left);
        }
    }
    return res;
};

function preorderTraversal(root: TreeNode | null): number[] {
    const res: number[] = [];
    const stack: TreeNode[] = root ? [root] : [];
    while (stack.length) {
        const node = stack.pop()!;
        res.push(node.val);
        if (node.right) {
            stack.push(node.right);
        }
        if (node.left) {
            stack.push(node.left);
        }
    }
    return res;
}

载入编辑器，自己跑一遍 →

其他解法

递归最简洁，显式栈避免递归深度限制，二者都要 O(h) 到 O(n) 空间；Morris 利用空闲指针把空间降到 O(1)。

解法 2：递归时间 O(n)，空间 O(n)

按照根、左子树、右子树的顺序递归。访问节点时先记录它的值，再依次递归左子树和右子树。

代码最短，直接对应定义。依赖系统调用栈，树退化成链时递归深度为 n。

import sys
from typing import List, Optional

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        sys.setrecursionlimit(10000)
        res = []

        def dfs(node):
            if not node:
                return
            res.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return res

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

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

class Solution {
    void dfs(TreeNode* node, vector<int>& res) {
        if (!node) return;
        res.push_back(node->val);
        dfs(node->left, res);
        dfs(node->right, res);
    }

public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        dfs(root, res);
        return res;
    }
};

func preorderTraversal(root *TreeNode) []int {
	res := []int{}
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		res = append(res, node.Val)
		dfs(node.Left)
		dfs(node.Right)
	}
	dfs(root)
	return res
}

var preorderTraversal = function(root) {
    const res = [];
    const dfs = (node) => {
        if (!node) return;
        res.push(node.val);
        dfs(node.left);
        dfs(node.right);
    };
    dfs(root);
    return res;
};

function preorderTraversal(root: TreeNode | null): number[] {
    const res: number[] = [];
    const dfs = (node: TreeNode | null): void => {
        if (!node) return;
        res.push(node.val);
        dfs(node.left);
        dfs(node.right);
    };
    dfs(root);
    return res;
}

解法 3：Morris 遍历时间 O(n)，空间 O(1)

对当前节点，若无左子树就记录并走向右子树。否则找到左子树中最右边的前驱节点。前驱的 right 为空时，记录当前节点，把前驱指向当前节点后进入左子树。前驱已指向当前节点时，说明左子树已遍历完，恢复指针后走向右子树。

不用栈和递归，额外空间 O(1)。会临时修改树的指针，逻辑较难理解。

from typing import List, Optional

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        cur = root
        while cur:
            if not cur.left:
                res.append(cur.val)
                cur = cur.right
                continue
            pre = cur.left
            while pre.right and pre.right is not cur:
                pre = pre.right
            if not pre.right:
                res.append(cur.val)
                pre.right = cur
                cur = cur.left
            else:
                pre.right = None
                cur = cur.right
        return res

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left == null) {
                res.add(cur.val);
                cur = cur.right;
                continue;
            }
            TreeNode pre = cur.left;
            while (pre.right != null && pre.right != cur) pre = pre.right;
            if (pre.right == null) {
                res.add(cur.val);
                pre.right = cur;
                cur = cur.left;
            } else {
                pre.right = null;
                cur = cur.right;
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode* cur = root;
        while (cur) {
            if (!cur->left) {
                res.push_back(cur->val);
                cur = cur->right;
                continue;
            }
            TreeNode* pre = cur->left;
            while (pre->right && pre->right != cur) pre = pre->right;
            if (!pre->right) {
                res.push_back(cur->val);
                pre->right = cur;
                cur = cur->left;
            } else {
                pre->right = nullptr;
                cur = cur->right;
            }
        }
        return res;
    }
};

func preorderTraversal(root *TreeNode) []int {
	res := []int{}
	cur := root
	for cur != nil {
		if cur.Left == nil {
			res = append(res, cur.Val)
			cur = cur.Right
			continue
		}
		pre := cur.Left
		for pre.Right != nil && pre.Right != cur {
			pre = pre.Right
		}
		if pre.Right == nil {
			res = append(res, cur.Val)
			pre.Right = cur
			cur = cur.Left
		} else {
			pre.Right = nil
			cur = cur.Right
		}
	}
	return res
}

var preorderTraversal = function(root) {
    const res = [];
    let cur = root;
    while (cur) {
        if (!cur.left) {
            res.push(cur.val);
            cur = cur.right;
            continue;
        }
        let pre = cur.left;
        while (pre.right && pre.right !== cur) pre = pre.right;
        if (!pre.right) {
            res.push(cur.val);
            pre.right = cur;
            cur = cur.left;
        } else {
            pre.right = null;
            cur = cur.right;
        }
    }
    return res;
};

function preorderTraversal(root: TreeNode | null): number[] {
    const res: number[] = [];
    let cur = root;
    while (cur) {
        if (!cur.left) {
            res.push(cur.val);
            cur = cur.right;
            continue;
        }
        let pre: TreeNode = cur.left;
        while (pre.right && pre.right !== cur) pre = pre.right;
        if (!pre.right) {
            res.push(cur.val);
            pre.right = cur;
            cur = cur.left;
        } else {
            pre.right = null;
            cur = cur.right;
        }
    }
    return res;
}

二叉树专题的其他题目

查看二叉树全部题目 →