考察点:递归与迭代两种思维、显式栈模拟调用栈、三种遍历在非递归下的差异(尤其后序的经典写法)。
要点:
print(root) 在 traverse(left) / traverse(right) 之间的位置(前:根左右;中:左根右;后:左右根),递归隐式用了调用栈。while (root || stack):先把 root 及其所有左孩子一路压栈,弹栈访问后 root 转向右孩子,再继续压它的左链。prev 指针判断「上次访问的是左还是右」决定下一步;或更简单的『前序变体(根右左)结果 reverse』技巧。参考实现(中序非递归):
function inorder(root) {
const res = [], stack = [];
while (root || stack.length) {
while (root) { stack.push(root); root = root.left; } // 一路向左
root = stack.pop();
res.push(root.val); // 出栈即访问
root = root.right; // 转向右子树
}
return res;
}
复杂度:时间 O(n),空间 O(h)(h 为树高,链表退化时 O(n))。
题目与答案就在本页;收藏、批注和错题重练在应用内