145. 二叉树的后序遍历

题目描述

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

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

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

示例 1

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

解释：3 是 2 的左孩子，2 是根的右孩子，根最后输出。

示例 2

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

解释：先输出左子树 4,6,7,5,2，再输出右子树 9,8,3，最后是根 1。

示例 3

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

解释：空树。

示例 4

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

数据范围

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

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

解题思路：反向前序后翻转

后序是“左 → 右 → 根”，它的反向是“根 → 右 → 左”，而后者只是把前序遍历里左右互换。所以用栈做一次“根 → 右 → 左”：弹出即记录，先压左孩子再压右孩子；最后把结果整体反转，就得到后序。

为什么正确

循环中 res 是“根 → 右 → 左”序列的前缀，反转后就是后序序列的后缀。

复杂度分析

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

易错点

这里压栈顺序是先左后右，和前序的写法刚好相反；最后一定要反转。仅把前序结果反转得到的是“右 → 左 → 根”，不是后序。

参考代码

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

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

class Solution {
    public List<Integer> postorderTraversal(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.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
}

class Solution {
public:
    vector<int> postorderTraversal(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->left) {
                stack.push_back(node->left);
            }
            if (node->right) {
                stack.push_back(node->right);
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

func postorderTraversal(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.Left != nil {
			stack = append(stack, node.Left)
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
	for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
		res[i], res[j] = res[j], res[i]
	}
	return res
}

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

function postorderTraversal(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.left) {
            stack.push(node.left);
        }
        if (node.right) {
            stack.push(node.right);
        }
    }
    return res.reverse();
}

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

其他解法

反向前序后翻转最好写，但只是结果等价；栈+前驱标记按真实后序访问节点，适合需要在后序位置处理的场景；递归最简洁。

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

按照左子树、右子树、根的顺序递归。先递归左右子树，最后记录当前节点的值。

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

import sys
from typing import List, Optional

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

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

        dfs(root)
        return res

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

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

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

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

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

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

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

解法 3：栈+前驱标记时间 O(n)，空间 O(n)

一路向左把节点压入栈。查看栈顶节点：若它有右子树且右子树还没访问过，就转向右子树。否则弹出并记录它，用 prev 记住刚访问的节点，用来判断右子树是否已处理。

按真正的后序顺序输出，不需要最后翻转，可以边遍历边处理。需要额外的 prev 判断，容易写错。

from typing import List, Optional

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res, stack = [], []
        cur, prev = root, None
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            node = stack[-1]
            if node.right and node.right is not prev:
                cur = node.right
            else:
                stack.pop()
                res.append(node.val)
                prev = node
        return res

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode cur = root, prev = null;
        while (cur != null || !st.isEmpty()) {
            while (cur != null) {
                st.push(cur);
                cur = cur.left;
            }
            TreeNode node = st.peek();
            if (node.right != null && node.right != prev) {
                cur = node.right;
            } else {
                st.pop();
                res.add(node.val);
                prev = node;
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        while (cur || !st.empty()) {
            while (cur) {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* node = st.top();
            if (node->right && node->right != prev) {
                cur = node->right;
            } else {
                st.pop();
                res.push_back(node->val);
                prev = node;
            }
        }
        return res;
    }
};

func postorderTraversal(root *TreeNode) []int {
	res := []int{}
	st := []*TreeNode{}
	cur := root
	var prev *TreeNode
	for cur != nil || len(st) > 0 {
		for cur != nil {
			st = append(st, cur)
			cur = cur.Left
		}
		node := st[len(st)-1]
		if node.Right != nil && node.Right != prev {
			cur = node.Right
		} else {
			st = st[:len(st)-1]
			res = append(res, node.Val)
			prev = node
		}
	}
	return res
}

var postorderTraversal = function(root) {
    const res = [], st = [];
    let cur = root, prev = null;
    while (cur || st.length) {
        while (cur) {
            st.push(cur);
            cur = cur.left;
        }
        const node = st[st.length - 1];
        if (node.right && node.right !== prev) {
            cur = node.right;
        } else {
            st.pop();
            res.push(node.val);
            prev = node;
        }
    }
    return res;
};

function postorderTraversal(root: TreeNode | null): number[] {
    const res: number[] = [], st: TreeNode[] = [];
    let cur: TreeNode | null = root, prev: TreeNode | null = null;
    while (cur || st.length) {
        while (cur) {
            st.push(cur);
            cur = cur.left;
        }
        const node = st[st.length - 1];
        if (node.right && node.right !== prev) {
            cur = node.right;
        } else {
            st.pop();
            res.push(node.val);
            prev = node;
        }
    }
    return res;
}

二叉树专题的其他题目

查看二叉树全部题目 →