递归
解题思路
确定递归函数的参数和返回值；
确定终止条件；
确定单层递归的逻辑；
复杂度
-
时间复杂度：
O(n)，其中 n 是二叉搜索树的节点数，每一个节点恰好被遍历一次； -
空间复杂度：
O(n)，为递归过程中栈的开销，平均情况下为O(logn)，最坏情况下树呈现链状，为O(n)；
代码实现
var postorderTraversal = function (root) {
// 用于存储遍历的结果
const res = [];
preorder(root, res);
return res;
};
const preorder = (root, res) => {
if (!root) return; // 当前结点为空时，无需进行递归
preorder(root.left, res); // 后序遍历左子树
preorder(root.right, res); // 后序遍历右子树
res.push(root.val); // 记录根节点值
}
反转前序遍历
解题思路
前序遍历是 中左右 的顺序，后续遍历是 左右中 的顺序（相对前序遍历只需要改动 3 行代码）；
只需要在前序遍历的基础上做少许改动即可，将 左右 的顺序颠倒变成 中右左 的顺序；
再将结果反转即可变成 左右中 的顺序；
复杂度
-
时间复杂度：
O(n)，其中 n 是二叉搜索树的节点数，每一个节点恰好被遍历一次； -
空间复杂度：
O(n)，为迭代过程中显式栈的开销，平均情况下为O(logn)，最坏情况下树呈现链状，为O(n)；
代码实现
var postorderTraversal = (root) => {
if (root === null) return [];
const stk = [root];
const res = [];
while (stk.length > 0) {
const node = stk.pop();
res.push(node.val);
if (node.left) stk.push(node.left);
if (node.right) stk.push(node.right);
}
return res.reverse();
}
迭代 + 栈
解题思路
后序遍历也叫 后根遍历 ，则遍历顺序为 左 -> 右 -> 根；
后序遍历的非递归算法比较复杂，因为后序非递归遍历二叉树的顺序是先访问左子树，再访问右子树，最后访问根节点；
先找到所有的左节点，将路径上的所有节点都入栈；
那对于根节点来说要被访问 3 次：
- 第 1 次经过它，去向左子树；
- 第 2 次从左子树回来，经过它，去向右子树；
- 第 3 次从右子树回退到它；
复杂度
-
时间复杂度：
O(n)，其中 n 是二叉搜索树的节点数，每一个节点恰好被遍历一次； -
空间复杂度：
O(n)，为迭代过程中显式栈的开销，平均情况下为O(logn)，最坏情况下树呈现链状，为O(n)；
代码实现
var postorderTraversal = function (curr) {
const res = []; // 存储处理结果
const stk = []; // 栈：存储根节点
let prev = null; // 记录被访问过的节点
while (curr || stk.length) {
// 找到最左端的节点，路径上的节点全部入栈,包括叶子节点
while (curr) {
stk.push(curr);
curr = curr.left;
}
// 获取栈顶节点
curr = stk[stk.length - 1];
if (curr.right === null || curr.right === prev) {
// 不存在右节点，说明 curr 是一个叶子节点，则接将该节点值入 res
// curr.right === prev，防止右节点被重复访问（右节点被重复入栈，因为右子树可能会有子节点，则该右子树的根节点就要入栈）
res.push(curr.val);
stk.pop();
prev = curr; // 记录最近访问过的节点
curr = null; // 将 node 置为空，避免下一次循环重复的添加 node 的左子树入栈
} else {
// 存在右节点，指针指向右子树，继续判断右子树是否有子节点
curr = curr.right;
}
}
return res;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 94. 二叉树的中序遍历
上一篇
评论
