LeetCode - 145. 二叉树的后序遍历
目录
题目
什么是后序遍历
递归写法
非递归写法
思路
过程
正确写法
题目
145. 二叉树的后序遍历 - 力扣（LeetCode）
什么是后序遍历
后序遍历（Post-order Traversal）是二叉树的三种主要遍历方式之一，遵循"左-右-根"的访问顺序：
- 首先遍历左子树（递归）
- 然后遍历右子树（递归）
- 最后访问根节点
简单来说，在后序遍历中，一个节点只有在其左右子树都被访问完后才会被访问。
1/ \2 3/ \ \
4 5 6后序遍历的结果是：[4, 5, 2, 6, 3, 1]
遍历过程：
- 访问左子树：先访问4，然后是5，最后是2
- 访问右子树：先访问6，然后是3
- 最后访问根节点1
递归写法
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;dfs(root,result);return result;}void dfs(TreeNode* root, vector<int>& result){if(!root){return;}dfs(root->left,result);dfs(root->right,result);result.push_back(root->val);}};非递归写法
采用两个栈来模拟实现左-右-根
思路
反序构建：
- 使用第一个栈(s1)进行类似前序遍历的操作，但是入栈顺序改为"先左后右"
- 这样从s1出栈的顺序就变成了"根-右-左"
- 将从s1出栈的元素依次压入第二个栈(s2)
- s2出栈时的顺序就是"左-右-根"，正好是后序遍历的顺序
操作步骤：
- 将根节点压入s1
- 当s1不为空时：
- 弹出s1栈顶节点并压入s2
- 将该节点的左子节点压入s1（如果存在）
- 将该节点的右子节点压入s1（如果存在）
- 当s1为空时，依次从s2弹出元素，这就是后序遍历的结果
原理解释：
- 第一个栈(s1)用于遍历树并产生"根-右-左"的顺序
- 第二个栈(s2)用于反转这个顺序，变成"左-右-根"
- 本质上是利用栈的后进先出特性，将一种顺序转换为它的反序
过程
步骤1：将根节点1压入s1
s1: [1]
s2: []步骤2：弹出s1栈顶元素1，压入s2，然后将1的子节点压入s1（先左后右）
s1: [2, 3] // 先左后右
s2: [1]步骤3：弹出s1栈顶元素3，压入s2，然后将3的子节点压入s1
s1: [2, 6] // 3只有右子节点
s2: [1, 3]步骤4：弹出s1栈顶元素6，压入s2（6没有子节点）
s1: [2]
s2: [1, 3, 6]步骤5：弹出s1栈顶元素2，压入s2，然后将2的子节点压入s1
s1: [4, 5] // 2的左右子节点
s2: [1, 3, 6, 2]步骤6-7：处理4和5（它们没有子节点）
s1: []
s2: [1, 3, 6, 2, 5, 4]步骤8：从s2中依次弹出元素得到结果
result = [4, 5, 2, 6, 3, 1]正确写法
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {//根在右，子在左vector<int> result;if(!root){return result;}stack<TreeNode*> st1;stack<TreeNode*> st2; st1.push(root);while(!st1.empty()){TreeNode* node = st1.top();st1.pop();st2.push(node);if(node->left){st1.push(node->left);}if(node->right){st1.push(node->right);}}while(!st2.empty()){TreeNode* cur = st2.top();result.push_back(cur->val);st2.pop();}return result;}
};